Bard College
Bard Digital Commons
Senior Projects Spring 2011 Bard Undergraduate Senior Projects
2011
Delaunay Diagram Representations for Use in
Image Near-Duplicate Detection
Adina R. Stoica
Bard College
is Access restricted to On-Campus only is brought to you for free and
open access by the Bard Undergraduate Senior Projects at Bard Digital
Commons. It has been accepted for inclusion in Senior Projects Spring
2011 by an authorized administrator of Bard Digital Commons. For more
information, please contact digitalcommons@bard.edu.
Recommended Citation
Stoica, Adina R., "Delaunay Diagram Representations for Use in Image Near-Duplicate Detection" (2011). Senior Projects Spring 2011.
Paper 52.
hp://digitalcommons.bard.edu/senproj_s2011/52
DelaunayDiagramRepresentations
ForUseinImageNear-DuplicateDetection
SeniorProjectsubmittedto
TheDivisionofScience,Mathematics&Computing
OfBardCollege
By
AdinaRalucaStoica
Annandale-on-Hudson,NewYork
May2011
TableofContents
Acknowledgements ....................................................................................................................................... 1
Abstract ......................................................................................................................................................... 2
1. Introduction ............................................................................................................................................... 2
2. What is an Image Near-Duplicate? ............................................................................................................ 5
3. Image Transformations Considered .......................................................................................................... 6
4. The Harris Corner Points Detector .......................................................................................................... 12
4.1. Introduction to the Harris Corner Detector ..................................................................................... 12
4.2. Motivation for the Harris Corner Detector ...................................................................................... 12
4.3. Mathematics behind the Harris Corner Detector ............................................................................ 13
4.4. Algorithm for the Harris Corner Detector ........................................................................................ 16
4.5. Why Use the Harris Corner Detector. Problems .............................................................................. 18
4.5. Invariant Corner Detector: Window Function .................................................................................. 19
4.6. MATLAB Code for Harris Corner Detector........................................................................................ 20
4.6.1. Discrete Convolution Matrices. 2-D Convolutions .................................................................... 20
4.6.2. The MATLAB program ............................................................................................................... 20
5. Graphs. Graph Similarity ......................................................................................................................... 23
5.1. Graphs. General Definitions ............................................................................................................. 23
5.1.1 Graphs. Finite Graphs. Simple Graphs. Vertex Degree .............................................................. 23
5.1.2. Walks. Trails. Paths. Cycles. Connected Graphs ........................................................................ 24
5.1.3. Directed Graphs ......................................................................................................................... 25
5.1.4. Weighted Graphs ....................................................................................................................... 25
5.1.5. Edge Crossings. Graph Faces. Planar Graphs. Plane Graphs. Dual Graphs ............................... 26
5.2. Graph Similarity. Possible Measures of Similarity ............................................................................ 28
5.2.1. Subgraphs. Induced subgraphs ................................................................................................. 28
5.2.2. Isomorphic Graphs .................................................................................................................... 29
5.2.3. Edge Contraction. Graph Minors ............................................................................................... 29
5.2.4. Chromatic Numbers .................................................................................................................. 30
5.2.5. Graph Diameter ......................................................................................................................... 31
5.3. Graph Representations .................................................................................................................... 31
6. Voronoi Diagrams And Delaunay Triangulations .................................................................................... 34
6.1. Theoretical Preliminaries ................................................................................................................. 34
6.1.1. Metric Spaces. The Euclidean Metric Space .............................................................................. 34
6.1.2. Convex Polytopes. Convex Polyhedrons ................................................................................... 35
6.1.3. Faces of a Convex Polytope/Polyhedron ................................................................................... 35
6.1.4. Simplices. Convex Hulls. Simple / Simplicial Polytopes ............................................................. 36
6.1.5. Cell Complexes. Triangulations ................................................................................................. 36
6.2. Voronoi Diagrams ............................................................................................................................. 37
6.2.1. Motivation ................................................................................................................................. 37
6.2.2. Voronoi Diagrams (Tessellations) .......................................................................................... 37
6.2.3. Properties of Voronoi Diagrams ................................................................................................ 39
6.3. Delaunay Triangulations ................................................................................................................... 40
6.3.1. Motivation ................................................................................................................................. 40
6.3.2. Delaunay Triangulations ............................................................................................................ 40
6.3.3. Properties of Delaunay Triangulations ...................................................................................... 41
7. MATLAB Functions: Voronoi, Voronoin, DelaunayTri, Qhull ................................................................... 43
7.1. Voronoi ............................................................................................................................................. 43
7.2. Voronoin ........................................................................................................................................... 44
7.3. DelaunayTri and triplot .................................................................................................................... 46
7.4. The Quickhull Algorithm ................................................................................................................... 47
8.1. Purpose ............................................................................................................................................. 49
8.2. Preliminaries ..................................................................................................................................... 49
8.3. Conditions ........................................................................................................................................ 50
8.3. Algorithm .......................................................................................................................................... 52
8.4. Problems........................................................................................................................................... 54
9. Encoding an Image as a Graph: Delaunay Triangulations ....................................................................... 56
9.1. Methodology .................................................................................................................................... 56
9.2. Encoding Code .................................................................................................................................. 57
9.3. Problems with Current Approach. Future Plans .............................................................................. 58
10. Results. Conclusions. Future Work ........................................................................................................ 60
10.1. Results ............................................................................................................................................ 60
10.2. Conclusions and Future Work ........................................................................................................ 72
Bibliography................................................................................................................................................. 75
Table Of Figures ........................................................................................................................................... 77
Table Of Code Snippets ............................................................................................................................... 79
1
A
CKNOWLEDGEMENTS
TheSeniorProjectrepresentsoneofthemostimportantstepsaBardstudenthastotake.
Itis theculminationoffouryears,inwhichonehasexperiencedlearningatits finest.WhenI
firstcametoBardfromRomania,Ididn’tknowwhatkindofroadIwasembarkingon,butIam
eversogladItookthechance.ThepeopleIhavemetandinteractedwithherehavechangedmy
lifeforthebetter,andtheclassesIhavetaken,aswellastheout-of-schoolopportunitiesIhave
been able to experience are unmatched in my home country. So, for starters, I would like to
thankBard,foracceptingmeandofferingmeaplaceinitsstudentbody,aswellastheDivision
ofScience,MathematicsandComputingformakingitpossible,financially,formetoattend.
FromtheamazinggroupofpeoplethatIhavemethere,Iwouldfirstandforemostliketo
warmly thank my Senior Project adviser, Robert McGrail, for the wealth of support he has
offered me not only through my Senior Project, but throughout the entire four years here—
THANKYOU
!IwouldalsoliketothanktheothermembersoftheComputerScienceDepartment
– Sven Anderson, Rebecca Thomas, Keith O’Hara – for their support, friendliness and
informationtheyhavegivenme,duringthese4years,aswellasthankotherprofessorsthathave
beeninvolvedinmySeniorProject,especiallyMaryKrembs,forthesuggestionsgivenaftermy
midwaypresentation.
Iamnowclosetotheendofmyperiodhere,andIknowthatIwillmissBard.Myfuture
guidesmetoSaintLouis,whereIwillbepursuingmyPh.D.inComputerScienceatWashington
University.Bardhashelpedmegrow up, andhastaughtmetobeanindependent,free-willed
adult:forthisIwillforeverbethankful!And,totheclassof2011:Congratulations!Wemadeit!
2
A
BSTRACT
GivenanimageoranimageDelaunayTriangulationdiagramrepresentation,
thepurposeofthisprojectistoidentifyanear-duplicateinanimagedatabase.
Thisisdonebycomputingthecornerpointsoftheimageundersomedefault
settings,usingtheVoronoidiagramtoadjustthesesettingsinordertogetbetter
adjustedcornerpointsfortheimage,andthenusingtheDelaunayTriangulation
of the image to identifywhetherthere are possible duplicates in the database.
The project investigates Voronoi Diagrams based on a default Harris Corner
Detectorasanimagesegmentationtechniqueforadjustingthethresholdforthe
Harris Corner Detector, as well as Delaunay Triangulation Diagrams as a
measureofsimilaritybetweenimages.Ultimately,theprojectfindsimagenear-
duplicatesinadatabasewithsomelikelihood.
1.
I
NTRODUCTION
Givenanimagetobesubmittedinadatabase(oruploadedontheInternet)wewouldlike
to know whether that specific image (under any transformations permitted by current image-
editingsoftware)isalreadyinthedatabase.Moreover,wewouldliketobeabletowithholdthe
actualimagefromtheduplicatedetectorwhenperformingthesearch,andinsteaduseadiagram
representationoftheimage,achievedusingtheDelaunayTriangulation.
Every image can be characterized to different degrees by various measures, such as
contrast difference, preponderancy of colors, wavelets, and entropy.There are some measures
thatareconservedundervariousimagetransformationssuchascropping,blurring,desaturation,
3
rotation, scaling, linear and non-linear changes in brightness, perspective distortion, noise,
changesinresolution,andfiltering.
Mainly,the aim of thisproject is to investigate image measures, specifically Delaunay
Triangulation Diagrams based on auto-adjusted Harris CornerPoints, that are better preserved
under some considered transformations and to develop an effective and efficient algorithm to
detect whether any near-duplicates for the image already exist in the database using these
measures.Therearethreestagesinwhichtheprojectisgoingtoachieveitsaim.Firstofall,the
Harris Corner Points Detection algorithm is used, under some default parameter settings, to
detectkeypointsintheimagethathaveanextremelikelihoodtomaintaintheirrelativeposition
withintheimageundervarioustransformations(theso-calledHarriscornerpoints,seesection4
and(Harris&Stephens,1988)),andtheVoronoiDiagramiscomputedusingthedetectedpoints.
Secondly,theVoronoiCellsthuscomputedareconsideredasanimagesegmentationmethodto
allowthecomputertoautomaticallyadjustthethresholdusedintheHarrisCornerDetector–the
new Harris Corner Points are computed using this new, auto-adjusted threshold. Lastly, the
efficiency of Delaunay Triangulation Diagrams (which are actually the dual graphs of the
Voronoi Diagrams) based on these new corner points is investigated in encoding important
featuresoftheimage,sothatthediagramcaneventuallybeusedinfindingnearduplicates–the
imagesareprobabilisticallymatchedbycomparingthefeaturesandstructuresofthesediagrams,
whilethepartsoftheimagethatareoutsidetheDelaunayDiagramarediscarded.
Imagematchingcanbedoneonpairsofimages,loadedfromadatabase,aswellasona
diagramrepresentationofoneimage,tobecomparedwithanimageinthedatabase;bothreduce
tothesamealgorithm.Eventuallytheprogramwouldallowtheusertoloadoneimage/Delaunay
representationandautomaticallysearchadatabaseofimages.Thegoalistodetectthelikelihood
4
that the loaded image/Delaunay representation is the near-duplicate of any other image in the
database.
Thestagesthealgorithm hastogothroughconsist offirstdetectingtheHarrisCorner
points for the image using a set value for the parameters (specifically the threshold) and
computingtheVoronoidiagrambasedonthethusdetectedcornerpoints,thenusingtheVoronoi
cellstoauto-adjustthethresholdparameterforabetterHarrisCornerPointsdetection,andthen
computingtheDelaunayTriangulationdiagramandusingvariousgraphsimilaritymeasuresto
determinewhetherornotwearedealingwithsimilargraphs.
5
2.
W
HATISAN
I
MAGE
N
EAR
-D
UPLICATE
?
Whileimageduplicatesareimagesthatareidenticalinallrespectstooneanother,image
near-duplicatesaretrickierandcanbesubjectedtodifferentinterpretations.Accordingto(Foo,
Zobe,&Sinha,2007),therearethreegroupsinwhichnear-duplicateshavebeencategorizedin
research literature, basedon the nature of the modifications of the original image: changes in
scene(wheretheobjectsplacedinsidethescenechangefromoneimagetoanother),changesin
camera (where the perspective of the camera changes between images) and changes in image
(whichareduetoimagetransformationsproducedbyimageeditingsoftware).
In my project I am only concerned with the last group, which deals with images that
havethe same digital source, and onlydiffer through changesappliedin post-production. The
factthattheimageshavethesamesourceshouldbeobviousforahumaninorderfortheimages
tostillbeconsiderednear-duplicatesbymydefinition–oncethesimilaritiesbetweentheimages
are blurred out for the human eye, it becomes even harder for a computer to identify them
(withoutaccessingphotoinformation).
Moreover, just like the human eye might not be able to distinguish between near-
duplicatepicturesthatfallintotheothertwogroups(changesinsceneandchangesincamera),
oneofthebiggestproblemsaworkingalgorithmmightencounterisfalsepositivesfallinginto
thosegroups.
6
3.
I
MAGE
T
RANSFORMATIONS
C
ONSIDERED
Fortestingpurposes,imagenear-duplicateswerecreatedandplacedinafolder.Theuser
hastheoptionofcreatingsomemorenear-duplicates byusingtheslideshow program.For the
purpose of this project, simple, linear, transformations of the image are considered. These
transformations can be grouped in different categories (of course various different grouping
criteriacanbechosen,suchasgeometricchangesversusphotometricchanges):
• Changesinimagesize/aspectratio:cropping,scaling(geometric)
• Changesinimageaspect:blurring,contrast,luminosity(photometric)
• Changesinimagecontent:rotation,reflection,horizontalshear(geometric)
In Figures 2 to 9, the basic transformations permitted by the slideshow program are
exemplifiedontheimageinFigure1.SeetheAnnexforapictureoftheinterfaceoftheprogram
andanexplanationaboutusingit.
Figure 1: Original Image
Cropping is achieved by using MATLAB’s function, imcrop, with the same starting
pointattheoriginoftheoriginalimageandthewidthandheightscaledto90%.
w=size(img,1); % get the width of the original image
h=size(img,2);
% get the height of the original image
7
img2=imcrop(img,[0,0,h*0.9,w*0.9]);
%
crop
image
to
90%
Code Snippet 1: Image Cropping
Figure 2: Cropped Image
Scalingtheimage(upordown)isdoneusingMATLAB’simresize—theimageisscaled
upby20%anddownby70%.
img2=imresize(img,1.2); % scale up
img2=imresize(img,0.3);
%
scale
down
Code Snippet 2: Image Scaling
Figure 3: Scaled Images (Up and Down)
8
Rotating,totheright,by 90degrees,isachievedusingMATLAB’simrotatefunction,
withthesecondargument-90,fortheangle.
img2=imrotate(img,-90); % rotate image 90 degrees, to the right
Code Snippet 3: Image Rotation, 90
o
Right
Figure 4: Image Rotated 90
o
Right
BlurringisdonebycreatingarotationallysymmetricGaussianlow-passfilterofsize10
withstandarddeviation10,usingMATLAB’sfspecialfunction,andapplyingittotheimage.
h = fspecial('gaussian',10,10); % define a Gaussian filter
img2=imfilter(img,h);
% apply the filter
Code Snippet 4: Image Blurring
Figure 5: Blurred Image
9
Horizontalreflection(ormirroring)isdonebyusingoneverycolorMATLAB’sfliplr
function.Sincethefunctiononlyworksongrayscaleimages,itisappliedoneverycolorchannel
componentoftheimage;thentheresultisunified.
img2 = []; %fliplr works with 2d matrices, so we have to
img2(:,:,1)=fliplr(img(:,:,1));
% flip the image
img2(:,:,2)=fliplr(img(:,:,2));
% around a horizontal axis
img2(:,:,3)=fliplr(img(:,:,3));
% component-by-component
img2=uint8(img2);
% convert to uint8, just in case
Code Snippet 5: Image Reflection
Figure 6: Horizontally Reflected Image
Auto-adjusting the contrast is done by equalizing the image histogram by using
MATLAB’shisteqfunction.Sincehisteqonlyworkswithgrayscale,2D,images,thefunctionis
applied on every color component of the image; then the image is unified. Without a second
parameter,histequsestheflathistogramasthedefaulthgram,andenhancesthecontrastofthe
image by transforming the values so that the histogram of the output image approximately
matchesthisflathistogram.ThealgorithmchoosesthegrayscaletransformationTtominimize
,wherec
0
isthecumulativehistogramoftheimage,andc
1
isthecumulative
sumofhistogramsforallintensitiesk.
10
img2 = [];
% histeq works with 2d matrices, so we have to do it
img2(:,:,1)=histeq(img(:,:,1));
% on every color component
img2(:,:,2)=histeq(img(:,:,2));
% of the RGB image
img2(:,:,3)=histeq(img(:,:,3));
% represented by a 3D matrix
img2=uint8(img2);
% cast to uint8, for certainty
Code Snippet 6: Image Auto-Contrast
Figure 7: Auto-Contrasted Image
AdjustingtheluminosityisdoneusingMATLAB’simadjust,whichtakestwovectorsof
RGBvalues–aninput(In)andanoutputvector(Out),whichbothhavetwocomponents:ahigh
componentandalowcomponent.Eachvectorhasform[lowRlowGlowB;highRhighGhighB],
andthevaluesbetweenthetwoper-color(lowandhigh)componentsofthefirst(In)vectorare
mappedtothevaluesbetweenthesamecomponentsofthesecond(Out)vector,whilethevalues
thatareoutsideoftheintervalofthefirstvectorgetclipped–theoneslowerthanlowColorinIn
getmappedtolowColorinOut,theoneshigherthanhighColorinIngetmappedtohighColorin
Out.Theemptyvector,[],defaultsto[000;111].
img2=imadjust(img,[0
0
0;
0
.8
0
.8
0
.8],[]);
%
brighten
image
% all values between 0 0 0 and .8 .8 .8 are mapped to values between
% 0 0 0 and 1 1 1; values above .8 .8 .8 map to 1 1 1.
%....
img2=imadjust(img,[0.2 0.2 0.2; 1 1 1],[]);
% darken image
Code Snippet 7: Image Brightness
11
Figure 8: Lighter and Darker Images
Horizontalsheartransformstheimagebyshearingithorizontallytotheleft,according
to the affine transformation matrix
. Shearing by this matrix slides the bottom
horizontalsideoftheimageby0.2totheright,creatingaparallelogram.Itisinterestinghowthis
transformcanaffectboththecornerdetectionandtheDelaunaysimilaritymeasure.
%defineahorizontalsheartransform
tform=maketform('affine',[100;0.210;001]);
img2=imtransform(img,tform);%applythetransformation
Code Snippet 8: Image Horizontal Shear
Figure 9: Horizontally Sheared Image
12
4.
T
HE
H
ARRIS
C
ORNER
P
OINTS
D
ETECTOR
4.1.IntroductiontotheHarrisCornerDetector
Moravec (Moravec H. , 1979) (Moravec H. , 1980) was the first who measured the
averagechangeofintensitybyshiftingalocalwindowbyasmallamountindifferentdirections.
TheHarrisCornerDetectormethodwasanimprovementonMoravec’sCornerDetectorandwas
firstdescribedinapaperpublishedin1988.Themotivationforacornerdetector,aswellasthe
algorithmandthemathematicsbehinditaredescribedbelow.Theprojectintendstoimprovethe
algorithm described in the paragraphs below by allowing the automatic adjustment of the
parameters(especiallythethreshold)inordertoachievebetter-fittedcornerpoints.
4.2.MotivationfortheHarrisCornerDetector
When using computer vision to understand the unconstrained 3D world, the viewed
scenesmightcontaintoomanyobjectsfortop-downrecognitiontechniquestowork.Inorderto
obtainanunderstandingofnaturalscenes(buildings,roads,trees,bushes,etc.),weneedtotrack
discreteimage features (which neither form a continuum,like atexture,norareedgepixels –
callededgels).
Inordertosuccessfullytrackobjectsin3D,theimagefeaturesweareinterestedinshould
be both corners (feature points) – which are discrete, reliable and meaningful, but are
disconnectedandarethereforelimitedinprovidinghigherleveldescriptions,suchasforsurfaces
and objects – and edges, which provide richer information, through their connectivity. Edge
connectivity and 3D locations of corners and junctions describe approximate 3D surfaces
throughawire-framestructuralrepresentationanddelimitedimageregions.
13
4.3.MathematicsbehindtheHarrisCornerDetector
The Harris Corner Detector is a method of determining the nature of a point by
computingtheaveragechangeofintensityintheimagewhenshiftingasmalllocalwindowin
theimagebyasmallamountinanydirection.Byshiftingthewindowinanydirectionbyone
pixel,wecandeterminethenatureofthepoint:iftheregionisflat,allshiftswillresultinonlya
smallchange;ifweareonanedge,ashiftalongtheedge(inanydirection)willresultinasmall
changeandashiftperpendiculartotheedgewillresultinalargechange;ifthepointisacorner,
allshifts(inatleastoneoftheoppositedirections)wouldresultinasignificantchange,asseen
inFigure10.
Figure 10: Harris Corner Detector
1
Thechangeproducedbyashiftofawindowwofsize(u,v)by(x,y)inanimagewith
intensitiesI,canbeexpressedby:
.
1
Figure from (Frolova & Simakov, March 2004)
14
Intheequationabove,Eisthechangeproducedbyashift,wisthewindowfunction,I
i
areimageintensitiesandthedifferencebetweenintensitiesisnearly0foraconstantpatch.Inthe
Harriscornerdetector,weareusingaGaussianwindow(
!
"
#$
"
"%
"
),coveringallpossiblesmall
shiftsbyperformingananalyticexpansionabouttheshiftattheoriginandmakinguseofthe
variationofEwiththedirectionofshift.
ByperformingaTaylorseriesexpansionofEabouttheorigin,thelocalautocorrelation
matrixisderivedusingfirstorderderivatives:
&'
(
)*
+
&, )', *
)*
-
(
)*
.
)*
,
)*&,
)*'
)*
/
(
)*
.
)*& ,
)*'/
(
)*
0
+
)*
&
-
, .
)*'/
,
)*
)*&'1
Here, I
x
=∂I/∂x and I
y
=∂I/∂y, the gradient vectors are a set of (dx, dy) points with a
center of mass defined as being at (0,0), and E is a close approximation of the local
autocorrelation function, with M describing its shape at theorigin (the quadratic terms in the
Taylorexpansion).Thelocalautocorrelationfunctionistherefore:
&'
+
& '
-
2
22
2 3
&
'
4,where 2
22
2
)*
5
6,
or
&'
+
& '
-
7
)*
5
683
&
'
4
Here,E(x,y)=tisanellipse,iftisaconstant(Figure11).Letλ
1
,λ
2
betheeigenvalues
ofM.Theeigenvaluesareproportionaltotheprincipalcurvaturesoftheautocorrelationfunction
15
E, and form a rotationally invariant description of M: the direction of fastest change is the
eigenvectorparalleltotheminoraxisoftheellipse(minimumeigenvalue)andthedirectionof
slowestchangeistheeigenvectorparalleltothemajoraxisoftheellipse(maximumeigenvalue).
Figure 11: Autocorrelation Function Graphical Representation
2
Insteadofcomputingeigenvalues,wewouldliketofindameasureofcornerandedge
qualityorresponsesizeoftheresponseusedtoselectisolatedcorerpixelsandtothintheedge
pixels.
Figure 12: Classification of Image Points Based on Response Size Using the Eigenvalues of M
3
2
Figure from (Frolova & Simakov, March 2004)
3
The figure is an adaptation of Figure 5 from (Harris & Stephens, 1988)
(λ
max
)
-1/2
(λ
min
)
-1/2
direction of the
slowest change
direction of the
fastest change
16
The paper (Harris & Stephens, 1988) finds an acceptable response function to be
9:;< = <>?@;=
, where :;< =λ
λ
, <>?@;=λ
, λ
and k is an empirical
constantbetween0.04and0.06.
FortheHarrisdetector,acornerregionpixel(i.e.onewithapositiveresponse)isselected
asanominatedcornerpixelonlyifitsresponseisan8-waylocalmaximum(Figure12).Edge
regionpixelsaredeemedtobeedgelsiftheirresponsesarebothnegativeandlocalminimain
eitherthexorydirections(inwhicheverdirectionthemagnitudeofthefirstgradientislarger).
In(Noble,1989),Noblefindsanotheradequateresponsefunction,R
2
ABCBDEFGHGCI
CDHJBI
K
L
"
K
M
"
K
N
K
M
"
K
L
"
K
M
"
,whereO 5
6.Thisfunctionhastheadvantagethatitdoesnotrelyona
(somewhatarbitrary)valuefork.
4.4.AlgorithmfortheHarrisCornerDetector
ThealgorithmbehindtheHarrisCornerDetectorisasfollows:
1. Computethexandyderivativesoftheimage,I
x
andI
y
2. Computetheproductsofderivativesateverypixel:I
x
2
,I
y
2
,I
x
I
y
3. Computethesumsoftheproductsofderivativesateachpixel,soastodefinethematrix
Mateachpixel:M
)*
5
6
4. ComputetheresponsedetectorRateachpixel:9:;<=
P>?@;=
5. ThresholdonvalueofR:
o FindpointswithlargecornerresponsefunctionR(R>threshold)
17
o Computenonmaxsuppression(takethepointsoflocalmaximaofR;suppressall
imageinformationthatisnotpartoflocalmaxima)
Scanimagealongtheimagegradientdirection
Ifpixelsarenotpartofthelocalmaximatheyaresettozero
Figure 13: Harris Corner Point Detection Workflow
4
Figure13,above,presentsasampleworkflowforthealgorithm.
4
Figure from (Frolova & Simakov, March 2004)
Original image: compute corner points
Compute the corner response R
Find points with large
corner response:
R > threshold
Locations of corner points in original image
Take only the points of local maxima of R
18
4.5.WhyUsetheHarrisCornerDetector.Problems
OneofthemostimportantreasonsforusingtheHarrisCornerPointDetectorasopposed
toothermeansisthefactthattheresultingcornerpointsareinvariantinpositiontomanyimage
transformations,suchastorotationsandpartiallytoaffineintensitychanges.
Figure 14: Rotation Invariance
5
Althoughthedetectedpointsarenotinvarianttoimagescale,therearewaystoovercome
thoseproblems.
Figure 15: The Harris Corner Detector is Not Invariant to Image Scaling
6
The rotation invariance is given bythefact that rotating an ellipse preserves its shape,
and therefore its eigenvalues, and the autocorrelation function (Figure 14). The Harris Corner
Point Detector is also partially invariant to affine intensity changes (i.e. linear scaling of
intensity) plus a constant offset, I
2
= aI + b (Figure 16). Since only derivatives are used, the
5
Figure from (Frolova & Simakov, March 2004)
6
Figures from (Frolova & Simakov, March 2004)
19
Harris Corner Point Detector is invariant to intensity shifts: I
2
= I + b, and also partially
insensitivetointensityscaling:I’=aI.
It is only partially invariant because sometimes intensity changes place some of the
originalcornerpointsaboveorbelowtheselectedthreshold,soaslongasthethresholddoesn’t
getreadjustedaccordingly,somepointswillbeincludedinoneoftheimagesandsomewillnot.
Unfortunately,theHarrisCornerdetectorisnotinvarianttoimagescaling(Figure15).
Whenanimageisscaled,cornersmaytransformtoedgesoredgesmaytransformtocorners.
Figure 16: Partial Invariance to Affine Intensity Change
7
4.5.InvariantCornerDetector:WindowFunction
Sincethepurposeofusingfeaturepointsistomatchimagesagainsteachother,itmakes
sensethatweareinterestedindetectingthesamecornerpointsregardlessofimagechanges.In
order for the same points to be computed, we need to adjust the threshold appropriately and
independentlywithineachoftheimages,insuchawaythatthewindowfunctionwouldidentify
thesamecornerpointsacrossbothimages.Thesolutionistodesignawindowfunctionsuchthat
it is scale invariant, i.e. the function changes as the scale changes. One example of such a
function, that would be appropriate if cropping was not considered as one of the image
transformations,istheaverageintensityoftheimage.
7
Figure from (Frolova & Simakov, March 2004)
20
4.6.MATLABCodeforHarrisCornerDetector
4.6.1.DiscreteConvolutionMatrices.2-DConvolutions
A convolution (Ahn, 2005) is a mathematical operation ontwo functions, producing a
thirdfunctionthatisamodifiedversionofoneoftheoriginalfunctions.Iffandgarefunctions
ofanintegervariablen,thentheformulaforthediscreteconvolutionoffandg,wheremisa
randominteger(time-shift),is:
QR S
T
( Q
U
ST U
VW
(Q
T U
SU
2D convolution is just extension of previous 1D convolution by convolving both
horizontal and vertical directions in 2 dimensional spatial domains. Iffandg arefunctions of
twodiscretevariables,n
1
andn
2
,thentheformulaforthetwo-dimensionalconvolutionoffand
g,eachshiftedbyk
1
andk
2
respectively,is:
T
T
QR S
T
T
( ( Q
T
T
ST
T
X
V
"
WX
V
Y
W
The MATLAB function conv2
uses a straightforward formal implementation of the two-
dimensional convolution equation (above) in spatial form. In practice
conv2
computes the
convolution for finite intervals.
4.6.2. The MATLAB program
The Harris Algorithm uses the response measure given by Nobel in her thesis. The
originalHarrismeasureiscommentedout.Theinputsofthefunctionaretheimageonwhichwe
areidentifyingcornerpoints,im,thestandarddeviationofsmoothingGaussian,sigma(withbest
21
values1to3),thethresholdthresh,andtheradiusofregionconsideredinnonmaxsuppression
radius(withbestvalues1to3).
Thefunctionreturnsthearraycim(ofthesamesizeasim)whichistheresponsedetector
ateachpixelaccordingto(Noble,1989),aswellasthe1Darraysrandc,whichrepresentthe
rowandcolumncoordinatesofthecornerpoints,respectively.Thealgorithmfirstcomputesthe
derivativesthatformmatrixO 5
6andtheresponsefunctionZU
ABCBDEFGHGCI
CDHJBI
K
L
"
K
M
"
K
N
K
M
"
K
L
"
K
M
"
.Then,nonmaxsuppressionisperformedsuchthatalltheinformationincimthatis
notpartofthelocalmaximaisdiscarded.
function[cim,r,c]=harris(im,sigma,thresh,radius)
error(nargchk(2,5,nargin));%validatethenumberofinputarguments
dx=[-101;-101;-101];%specialmatrixforconvolution
dy=dx';%thetransposeofdx,alsousedforconvolution
%Computethexandyderivativesoftheimage,IxandIy
Ix=conv2(single(im),single(dx),'same');
Iy=conv2(single(im),single(dy),'same');
g=fspecial('gaussian',max(1,fix(6*sigma)),sigma);%Gaussianfilter
%Computetheproductsofderivativesateverypixel:Ix^2,Iy^2,IxIy
Ix2=conv2(single(Ix.^2),single(g),'same');
Iy2=conv2(single(Iy.^2),single(g),'same');
Ixy=conv2(single(Ix.*Iy),single(g),'same');
%cimisthedeterminant/trace
cim=(Ix2.*Iy2-Ixy.^2)./(Ix2+Iy2+eps);
%k=0.04;
%cim=(Ix2.*Iy2-Ixy.^2)-k*(Ix2+Iy2).^2;
%Thresholdoncim
ifnargin>2
sze=2*radius+1;
mx=ordfilt2(cim,sze^2,ones(sze));
%Findlocalmaxima
cim=(cim==mx)&(cim>thresh);
[r,c]=find(cim);
end
Code Snippet 9: Harris Corner Detector Function
AfewnotesontheMATLABpre-definedfunctionsusedinthecode:
22
• error(MSG)displayserrormessageMSGandabortsfunction;
• nargchk(LOW,HIGH,N)returnsanappropriateerrormessagestringifNisnotbetween
LOWandHIGHandanemptymatrixotherwise;
• narginreturnsthenumberofinputargumentsthatwereusedtocallthefunction;
• single(X)convertsconvertthevariableXtosingleprecisionforlessstoragespace;
• conv2(A,B,'same')computesthe2DconvolutionofAandBandreturnsthecentralpart
oftheconvolution(basicallytheintensityderivativesI
x
,I
y
,I
x
I
y
,I
x
2
,I
y
2
);
• fspecial(‘gaussian',HSIZE,SIGMA)returnsapredefined,rotationallysymmetricGaussian
lowpassfilterofsizeHSIZEwithstandarddeviationSIGMA(positive);
• ordfilt2(A,ORDER,DOMAIN)computesthe2Dorder-statisticfilteringbyreplacingeach
elementinAbytheORDER-thelementinthesortedsetofneighborsspecifiedbythe
nonzeroelementsinDOMAIN;
• epsreturnsthedistancefrom1.0tothenextlargerdoubleprecisionnumber(=2
-52
);
• ones(sze)returnsa1-by-szematrixofones;
• find(X)returnsthelinearindicescorrespondingtothenonzeroentriesofthearrayX.
23
5.
G
RAPHS
.
G
RAPH
S
IMILARITY
The definitions and examples in this chapter are taken from (West, 1996, 2001),
(MathWorks, 1984-2011), (Bondy & Murty, 1976), (William & Hirschfeld, 2001), sometimes
verbatim.Theyareprovidedasthetheoreticalbackgroundfortheproject.
5.1.Graphs.GeneralDefinitions
5.1.1Graphs.FiniteGraphs.SimpleGraphs.VertexDegree
Definition:AgraphGisatripleconsistingofavertexsetV(G),anedgesetE(G),anda
relationthatassociateswitheachedgetwovertices(notnecessarilydistinct),calledendpoints.
Agraphisfiniteifitsvertexsetandedgesetarefinite.Everygraphcomputedonimages,
as done in this project, is finite. Drawing a graph means placing the vertices as points in the
planeandrepresentingtheedgesascurvesjoiningthelocationsoftheirendpoints.
Figure 17: Graph (G) Example
Example:
Inthegraph(Figure17)totheleft:
• thevertexsetisV={x,y,z,w}
•
theedgesetisE={e
1
=wx,e
2
=wx,e
3
=wz,e
4
=wz,e
5
=wy,e
6
=xy,e
7
=yz}
Forthepurposesofthisproject,thegraphswearedealingwitharesimplegraphs,which
aregraphsthathavenoloops(edgeswhosetwoendpointsarethesame)ormultipleedges(edges
havingthesamepairofendpoints).Inotherwords,ingraphGinFigure17,edgese
1
ande
2
are
notdifferentedges,andneitherareedgese
3
ande
4
.
24
Avertexvandanedgeeareincidentifvisanendpointofe.Inthiscase,wecallean
incidentedgeofv.Thedegreeofavertexisthenumberofincidentedgesforthatvertex.
5.1.2.Walks.Trails.Paths.Cycles.ConnectedGraphs
Definition: A walk in G is a finite non-null sequence W = v
0
e
1
v
1
… e
k
v
k
of vertices and
edges suchthatfor1≤i≤k,theedgee
i
hasendpointsv
i-1
andv
i
.WesaythatWisawalkfrom
v
0
tov
k
,orav
0
,v
k
–walk.Inasimplegraph,awalkv
0
e
1
v
1
… e
k
v
k
isdeterminedbythesequence
v
0
v
1
… v
k
ofitsvertices; henceawalkinasimplegraph canbespecified simplybyitsvertex
sequence.
A trail is walk with no repeated edges. A path is a trail with no repeated vertices. A
u,v–path is a path whose vertices of degree 1 (its endpoints) are u and v and the others are
internalvertices.
TwoverticesuandvofGaresaidtobeconnectedifthereisau,v–pathinG.Agraphis
connectedifallofitsverticesareconnected.
Awalk:uavfyfvgyhwbv
Atrail:wcxdyhwbvgy
Apath:
xcwhyeuav
Samplecycles:wcxdyhwand
yhwbvgy
Figure 18: Example of Walk, Trail, Path, and Cycles
8
A walk is closed if it has positive length and its origin and terminus are the same. A
closedtrailwhoseoriginandinternalverticesaredistinctiscalledacycle.
InFigure18,wehaveexamplesofawalk,atrail,apath,andtwocycles.
8
The figure is adapted from Figure 1.8 of (Bondy & Murty, 1976)
25
5.1.3.DirectedGraphs
Definition:AdirectedgraphordigraphGisatripleconsistingofavertexsetV(G),an
edgesetE(G),andafunctionassigningeachedgeanorderedpairofvertices(Figure19).The
firstvertexoftheorderedpairisthetailoftheedge,andthesecondisthehead;together,they
arecalledtheendpoints.Wesaythatanedgeisanedgefromitstailtoitshead.
In this project we are only considering undirected graphs, since there is no specific
directionforedgeswhenconstructingtheVoronoiDiagram.
Figure 19: A Directed Graph
5.1.4.WeightedGraphs
A weighted graph is a graph with numerical labels on its edges. These labels can
represent a varietyof costs, such as distance, price, time etc. Inthe project, weighted graphs,
withweightsbeingactualdistancesbetweenthetwoendpointsoftheedges(i.e.thelengthsof
theedges)wereconsidered.Ultimately,forthisstageoftheproject,Ihaveneverthelessoptedfor
unweighted graphs, though distances have the potential of eliminating many false positive
results.
26
5.1.5.EdgeCrossings.GraphFaces.PlanarGraphs.PlaneGraphs.DualGraphs
Definition: A curve is the image of a continuous map from [0,1] to ℝ
2
. A polygonal
curveisacurvecomposedoffinitelymanylinesegments.Itisapolygonal u,v–curvewhenit
startsatuandendsatv.
AdrawingofagraphGisafunctionfdefinedonV(G)∪E(G)thatassignseachvertexv
apointf(v)intheplaneandassignseachedgewithendpointsu,vapolygonalf(u),f(v)–curve.
Theimagesofverticesaredistinct.Apointinf(e)∩f(e’)thatisnota commonendpointisa
crossing.
Definition:Agraphisplanarifithasadrawingwithoutcrossings.Suchadrawing is
called a planar embedding of G. A plane graph is a particular planar embedding of a planar
graph.
Figure 20: The Cube Graph; Edge Crossing; Planar Representation
9
ThefirstrepresentationinFigure20showsaspecialtypeofgraph,thecubegraph;the
second representation shows the edge crossings, while the third representation shows a re-
drawingwithoutedgecrossings.Therefore,thecubegraphisaplanargraph.
Definition:AnopensetintheplaneisasetU⊆ℝ
2
suchthatforeveryp∈U,allpoints
within some small distance from p belong to U. A region is an open set U that contains a
polygonalu,v–curveforeverypairu,v∈U.Thefacesofaplanegrapharethemaximalregions
9
Image adapted from: (Winter)
27
oftheplanethatcontainnopointusedintheembedding.Thefacesarethustheregionsbounded
bytheedgesofthegraph.
Figure 21: Faces of a Graph
10
Figure21showsthefacesofagraph,eachcoloredinadifferentcolor.Theexteriorface,
coloredinyellow,iscalledaninfiniteface.
Figure 22: Dual Graphs
11
Definition: The dual graph G
*
of a plane graph G is a plane graph whose vertices
correspondtothefacesofGandwhoseedgescorrespondtotheedgesofGasfollows:ifeisan
edgeofGwithfaceXononesideandfaceYontheother,thentheendpointsofthedualedge
e
*
∈ E(G
*
)aretheverticesx,y∈G
*
thatrepresentthefacesX,YofG.Theorderintheplaneof
theedgesincidenttox∈V(G
*
)istheorder of the edgesbounding the faceXofG in awalk
alongitsboundary.
10
Image taken from (Winter)
11
Image taken from (Winter)
28
In
Figure22
,theoriginalgraphisdrawninblack,anditsdualisdrawninred.Itis
important to note that, as defined in Chapters 6 and 7, Voronoi Graphs and Delaunay
Graphsaredualgraphs.
5.2.GraphSimilarity.PossibleMeasuresofSimilarity
In this project, we are concerned with what makes two graphs related, and more
specificallywithmeasuresofsuchconnectedness.Inthesimplestsense,twoDelaunaygraphsof
thesameimagewouldbeidentical
,bothinnumberofvertices,edgeconnectionsandinvertex
labeling. In the same way, the graphs of scaled and sheared images would be identical to the
originalgraphifdistancesbetweenverticesdonotmatter(sothegraphsarenotweighted)and
thegraphsofrotatedandreflectedimageswouldbeidenticalbutwithdifferentvertexlabeling(a
graph isomorphic
to the original). The graphs of cropped images would be subgraphs of the
originalimagegraph,andthesimilaritybetweentheoriginalimageandtheimagesobtainedby
blurring, contrast auto-adjustment, and changing luminosity will consist of either induced
subgraphs
of the original graph or of minors of the original graph. Other similarity measures
consideredarechromaticnumbers
andthegraphdiameter.
5.2.1.Subgraphs.Inducedsubgraphs
Definition:AsubgraphofagraphGisagraphHsuchthatV(H)⊆V(G)andE(H)⊆
E(G)andtheassignmentofendpointstoedgesinHisthesameasinG.
AsubgraphHisaspanningsubgraphofagraphGifHandGhavethesamevertexset.
WethensaythatHspansG.HisaninducedsubgraphofGif,foranypairofverticesuandvof
H,uvisanedgeofHifandonlyifitalsoisanedgeofG,thatisifHhasexactlythesameedges
29
ofGoveritsvertexset.IfthevertexsetofHisthesubsetSofthevertexsetofG,V(G),thenwe
cansayHisinducedbySandwriteHasG[S].
5.2.2.IsomorphicGraphs
Definition:Anisomorphism from a simple graph G to a simplegraphHis abijection
f:V(G)→V(H)suchthatuv∈E(G)ifandonlyiff(u)f(v)∈E(H).Ifthereisanisomorphism
betweenGandH,thenGisisomorphictoH.
For example, the graphs G
1
and G
2
on page 32 are isomorphic to each other, and the
isomorphismf:V(G
1
)→V(G
2
)isgivenby:f(1
1
)=3
2
,f(2
1
)=4
2
,f(3
1
)=1
2
,f(4
1
)=2
2
.
5.2.3.EdgeContraction.GraphMinors
ThecontractionofanedgeeofGwithendpointsuandvisthedeletionofesuchthatits
endpointsuandvareidentifiedandtheedgesincidenttothenewvertexaretheedges,otherthan
e,thatwereincidenttouortov;theresultinggraphisdenotedbyG·eandhasonelessedge
thanG.AnexampleofedgecontractionisgiveninFigure23.
Definition: A graph H is a minor of another graph G if H can be obtained from a
subgraphofGbyedgecontraction.AnequivalentdefinitionstatesthatHisaminorofGifthere
isamapthatassociateswitheachvertexvofHanon-empty,connectedsubgraphG
v
ofGsuch
thatG
v
andG
u
aredisjointforu≠vandifthereisanedgebetweenuandvinHthenthereisan
edgeinGbetweensomevertexinG
v
andsomevertexinG
u
.
InFigure23,thegraphontherightisaminorofthegraphontheleft.
Unfortunately for the relative execution time of the graph-based image matching
program, the determination of graph minors is an NP-hard problem for which no good
30
algorithmsareknown(WolframResearch,2011).Nevertheless,brute-forcemethodsexist,such
asthosegivenbyRobertson,Sanders,andThomasin(Barber,Dobkin,&Huhdanpaa,1996).
Figure 23: Contracting edge v
1
v
2
to vertex `
a
12
5.2.4.ChromaticNumbers
Definition:Ak-coloringofagraphGisalabelingf:V(G)→S,where|S|=k.Thelabels
arecolors;theverticesofonecolorformacolorclass.Ak-coloringisproperifadjacentvertices
havedifferentlabels.Agraphisk-colorableifithasaproperk-coloring.Thechromaticnumber
χ(G)istheleastksuchthatGisk-colorable.
Figure 24: Graph Coloring Examples with χ = 3
12
The image is taken from (Hadwiger, 1998)
31
5.2.5.GraphDiameter
Definition: If G has a u,v–path, then the distance from u to v, written as d
G
(u, v) or
simplyd(u, v) is the leastlengthof a u,v–path. If G has no such path, then d(u, v) = ∞. The
diameterofagraphG,diam(G),isthemaximumsuchdistance,max
u,v
∈
V(G)
d(u,v).
In other words, a graph's diameter is the largest number of vertices which must be
traversedinordertotravelfromonevertextoanotherwhenpathswhichbacktrack,detour,or
loopareexcludedfromconsideration(WolframResearch,2011).
Figure 25: Graph Diameter Example
13
InFigure25,allthegraphshave10verticesanddiameter3,4,5,and7,respectively.
5.3.GraphRepresentations
Definition:An adjacency matrix of a graph G, A(G), is, the n-by-n(square) matrix in
whichentrya
i,j
isthenumberof edgesinGwithendpoints{v
i
,v
j
}.Anincidencematrixofa
graphG,M(G),isthen-by-mmatrixinwhichm
i,j
is1ifv
i
isanendpointofe
j
,and0otherwise.
Incomputerscience,graphsaremostoftenrepresentedusingtheadjacencymatrix.Note
that,forsimplegraphs,theadjacencymatrixisthesquarematrixinwhichentrya
i,j
is1ifthereis
anedgewithendpoints{v
i
,v
j
}and0otherwise.Also,sincethegraphswearedealingwithare
13
The image was taken from (Wolfram Research, 2011)
32
not oriented graphs, the adjacency matrix is symmetric about the principal diagonal, whose
entriesareall0.
Figure 26: Graph G
1
Representations
A graph can also be representedbyitsdegreesequence, where a degreesequence is a
monotonic non-increasing sequence of the vertex degrees of its vertices.For example, for the
graphinFigure26,thedegreesequenceis{3,2,2,1}.SincethegraphinFigure27hasthesame
degreesequence,itbecomesapparentthattheyareinfactthesamegraph(anisomorphism).
Figure 27: Graph G
2
Representations
Anothermethodtorepresentgraphsthatissometimesusedincomputerscience(andis
alsousedinsomeoftheMATLABfunctionsemployedinthisproject)impliestwoarrays:one
arrayrepresentingtheverticesofthegraph(eitherin1D,containingthevertexlabels,orin2D,
1 2 3 4
1 0 1 1 0
2 1 0 1 0
3 1 1 0 1
4 0 0 1 0
a b c n
1 1 0 0 1
2 1 1 0 0
3 0 1 1 1
4 0 0 1 0
Adjacency Matrix A
1
(G
1
) Incidence Matrix M
1
(G
1
) Graph G
1
1 2 3 4
1 0 1 1 1
2 1 0 0 0
3 1 0 0 1
4 1 0 1 0
a b c n
1 1 1 1 0
2 1 0 0 0
3 0 1 0 1
4 0 0 1 1
Adjacency Matrix A
2
(G
2
) Incidence Matrix M
2
(G
2
) Graph G
2
d
d
33
containingthecoordinatesforeachvertex),andtheotheronerepresentingtheedgeconnections.
Inthesimplestimplementation,thissecondarrayis2-dimmensionalandcontainsthetwoindices
oftheverticesinthefirstarraythatconstitutetheendpointsofeachedge.Ifthefirstarrayis1D,
sometimesitcanbeomittedandthevertexindicesinthesecondarraycanbereplacedwiththe
actual labels of the vertices. In more complicated cases, the second array can be multi-
dimensional, and contain all cycles in the graph with every edge represented only once (the
MATLABdatastructureforarrayswithinarraysorarraysofmatricesiscalledacell).
Forexample,forgraphG
1
inFigure26,wehavethevertexmatrixV
1
=[1,2,3,4]and
theedgematrixE
1
=[[1,2],[1,3],[2,3],[3,4]].
34
6.
V
ORONOI
D
IAGRAMS
A
ND
D
ELAUNAY
T
RIANGULATIONS
The definitions and other theoretical aspects in this chapter are taken from (Dirichlet.,
1850),(Voronoi,1908),(Fukuda,2004),(Rosenlicht,1985),(AurenhammerF.)andLectures16
and17of(Pless,2003),sometimesverbatim.Theyareprovidedinordertogiveabackground
intothecomputationalgeometryconstructsusedasabasisfortheproject.
6.1.TheoreticalPreliminaries
Pleasenotethat,althoughgeneraldefinitionsaregiveninwhatfollows,wearedealing
withonlytwodimensions,son=2.
6.1.1.MetricSpaces.TheEuclideanMetricSpace
Definition:AmetricspaceisasetE,togetherwitharulewhichassociateswitheachpair
p,q∈Earealnumberd(p,q)suchthat:
1. d(p,q)≥0forallp,q∈E
2. d(p,q)=0ifandonlyifp=q
3. d(p,q)=d(q,p)forallp,q∈E
4. d(p,r)<d(p,q)+d(q,r)forallp,q,r∈E(triangleinequality).
Thus a metric space is an ordered pair (E, n), where E is a set and n is a function
n:E
2
→Rsatisfyingproperties(1)to(4).
ForanypositiveintegernwedefineametricspaceE
n
,calledann-dimensionalEuclidean
space,bytakingtheunderlyingsetofE
n
tobealln-tuplesofrealnumbers{(a
1
,…,a
n
)|a
i
∈ℝ},
anddefining,forp=(x
1
,…,x
n
),q=(y
1
,…,y
n
),
35
c
de
f
&
'
, &
'
, g,&
V
'
V
Thatis,theEuclideanmetricistheordinarydistanceusedintheday-to-dayworldand
thatisgivenbythePythagoreanformula.Themetricspaceassumedintheproject,forallthe
typesofdiagramsdefined,istheEuclideanSpace.
6.1.2.ConvexPolytopes.ConvexPolyhedrons
Definition:AsubsetPofℝ
n
iscalledaconvexpolyhedronifitisthesetofsolutionstoa
finitesystemoflinearinequalities,andcalledaconvexpolytopeifitisaconvexpolyhedronand
itisalsobounded.Whenaconvexpolyhedron(orpolytope)hasdimension k,itiscalledak-
polyhedron(orak-polytope).
6.1.3.FacesofaConvexPolytope/Polyhedron
Definition:LetPbeaconvexn-polyhedron(orn-polytope)inℝ
n
.Forarealn-vectorc
andarealnumbern,alinearinequalityc
T
x≤niscalledvalidforPiftheinequalityholdsforall
x ∈ P. A subset F of a polyhedron P is called a face of P if it is represented as
hi ∩ j&k@
l
&mnforsomevalidinequalityc
T
x≤n.
Bythisdefinition,boththeemptysetØandthewholesetParefaces.Thesetwofaces
arecalledimproperfaceswhiletheotherfacesarecalledproperfaces.
Wecanalsodefinefacesgeometrically.Ahyperplanehofℝ
n
issupportingPifoneof
thetwoclosedhalf-spaces(oneofthetwopartsintowhichaplanedividesthethree-dimensional
space)ofhcontainsP.AsubsetFofPiscalledafaceofPifitisØ,Pitselfortheintersectionof
Pwithasupportinghyperplane.
The faces of dimension 0, 1, dim(P)–2 and dim(P)–1 are called the vertices, edges,
ridges and facets, respectively. The vertices coincide with the extreme points of P which are
36
definedaspointswhichcannotberepresentedasconvexcombinationsoftwootherpointsinP.
Whenanedgeisnotbounded,therearetwocases:eitheritisalineorahalf-linestartingfroma
vertex.Ahalf-lineedgeiscalledanextremeray.
6.1.4.Simplices.ConvexHulls.Simple/SimplicialPolytopes
Definition: For a subset
S
of
ℝ
n
, the convex hull,
conv(S),
is defined as the smallest
convex set in
ℝ
n
containing S. The convex hull computation means the “determination” of
conv(S)foragivenfinitesetofnpointsS={p
1
,p
2
,…,p
n
}inℝ
n
.
IfSisfinite,theconvex
hulldefinesamatrixAandavectorbsuchthatforallxinS,Ax+b<=[0,...].
Definition:AsubsetPofℝ
n
iscalledak-simplex(k=0,1,2….)ifitistheconvexhull
ofk+1affinelyindependentpoints.Ithasexactlyk+1verticesandk+1facets.
An n-polytope is called simple if each vertex is contained in exactly n facets. An
n-polytopeiscalledsimplicialifeachfacetcontainsexactlynvertices.Bydefinition,adualofa
simplepolytopeissimplicialandtheotherwayaround.Everyfacetofasimplicialn-polytopeis
a(n–1)–simplex.Eachvertexofasimplen-polytopeiscontainedinexactlyn-edges.
6.1.5.CellComplexes.Triangulations
Definition: A cell complex (a complex) in ℝ
n
is a set K of convex polyhedra (called
cells)inℝ
n
satisfyingtwoconditions:
1. Everyfaceofacellisacell(i.e.inK),and
2. IfPandP’arecells,thentheirintersectionisacommonfaceofboth.
Asimplicialcomplexisacellcomplexwhosecellsareallsimplices.
37
Thebody|K|ofacomplexKistheunionofallcells.WhenasubsetPofℝ
n
isthebody
ofasimplicialcomplexK,thenKissaidtobeatriangulationofP.ForafinitesetSofpointsin
ℝ
n
,atriangulationofSisasimplicialcomplexKwith|K|=conv(S).
6.2.VoronoiDiagrams
6.2.1.Motivation
First studied by Voronoi (Voronoi, 1908) and Dirichlet (Dirichlet., 1850), the
Voronoi/Dirichlet spatial tessellations have applications in a variety of disciplines, including
image compression, epidemiology, climatology, deriving the capacity of wireless networks,
computer graphics, robot navigation, cellular biology, statistics, the territorial behavior of
animals etc. (Aurenhammer & Klein, 2000), (Okabe, Boots, Sugihara, & Chiu., 2000), (Du,
Faber, & Gunzburger, 1999). In this project, Voronoi diagrams are used as an image
segmentationmethodforauto-adjustingthethresholdinordertoobtainthebestpossibleHarris
Corner Points to generate the best Delaunay Triangulation for each of the two images to be
compared.
6.2.2.
Voronoi Diagrams (Tessellations)
Definition: A Voronoi diagram (also called a Voronoi tessellation, Voronoi
decomposition, or Dirichlet tessellation) is a special kind of decomposition of a metric space
determinedbydistancestoaspecifieddiscretesetofobjectsinthespace(usuallydenotedbya
setofpoints),accordingtothenearest-neighborrule,suchthateachpointisassociatedwiththe
regionoftheplaneclosesttoit.
GivenS={p
1
,p
2
,...,
p
thepartitionofℝ
n
inton
polyhedral
isdefinedasthesetofpointsin
ℝ
The set of all Voronoi
cells
complex are called the Voronoi
Voronoi rays. For each point v
points,p∈S–v,whichare
closest
pointv∈ ℝ
m
tobeaVoronoi
vertex
Another way to define
Vo(
sitesp
i
andp
j
,thesetofpoints
that
whose bounding line is the
perpendicular
h(p
i
,p
j
).Thenapointqliesin
V(
j
≠
i.Inotherwords,
14
Image taken from (Fukuda, 2004)
p
n
},asetofndistinctpoints(sites)inℝ
n
,the
Voronoi
polyhedral
regions,Vo(p),calledtheVoronoicellsof
p
ℝ
n
whichareclosertopthantoanyothersite,
or
,wheredistheEuclidean
distance
cells
and their faces formsa cell complex.
The
vertices, and the extreme rays (i.e.
unbounded
∈ ℝ
m
, the nearestneighborsetnb(S, v) of v
in
closest
tovinEuclideandistance.Alternatively,
one
vertex
ofSifnb(S,v)ismaximaloverallnearest
neighbor
Figure 28: Voronoi Diagram
14
Vo(
p
i
) is in terms of the intersection ofhalf-
planes.
that
arestrictlyclosertop
i
thantop
j
isjust
the
perpendicular
bisector between p
i
and p
j
.
Denote
V(
p
i
)ifandonlyifqlieswithintheintersection
of
.
38
Voronoi
diagramis
p
.AVoronoicell
or
moreprecisely,
distance
function.
The
vertices of this
unbounded
edges) are the
in
S is the set of
one
candefinea
neighbor
sets.
planes.
Given two
the
openhalf-plane
Denote
this half-plane
of
h(p
i
,p
j
)forall
39
6.2.3.PropertiesofVoronoiDiagrams
Voronoiedges:EachpointonanedgeoftheVoronoidiagramisequidistantfromitstwo
nearestneighborsp
i
andp
j
.Thus,thereisacirclecenteredatsuchapointsuchthatp
i
andp
j
lie
onthiscircle,andnoothersiteisinteriortothecircle.
Voronoi vertices: It follows that vertex at whichthreeVoronoi cells V(p
i
), V(p
j
), and
V(p
k
) intersect isequidistant from all sites. Thus it is the center of the circle passing through
thesesites,andthiscirclecontainsnoothersitesinitsinterior.
Degree:Ifweassumethatnofourpointsareco-circular,thentheverticesoftheVoronoi
diagramallhavedegreethree.
Convex hull: A cell of the Voronoi diagram is unbounded if and only if the
correspondingsiteliesontheconvexhull.(Observethatapointisontheconvexhullifandonly
ifitistheclosestpointfromsomepointatinfinity.)
Size:Ifndenotesthenumberofsites,thentheVoronoidiagramisaplanargraph(ifwe
imaginealltheunboundededgesasgoingtoacommonvertexinfinity)withexactlynfaces.It
follows from Euler's formula that the number of Voronoi vertices is at most 2n – 5 and the
numberofedgesisatmost3n–6.
Voronoi diagrams can be represented as graphs, where the Voronoi edges described in
Section6.2.2arethegraph’sedges,andtheVoronoiverticesarethegraph’svertices.Generating
Voronoidiagramsbasedonfeaturepointsenablesustoascertainwhichregionintheimageis
bestcharacterizedbythegeneratingfeaturepointembedded.
6.3.Delaunay
Triangulations
6.3.1.Motivation
The dual of the
Voronoi
Triangulation using the best
(auto
originalimageandonallthe
images
TheDelaunaygraphsarethen
compared
representedasDelaunay
diagram
6.3.2.Delaunay
Triangulations
The vertices for the
Delaunay
Since (assuming general
position)
follows that the faces of the
dual
resultingdualgraphisa
triangulation
Figure
Let
S
beasetof
m
points
set of a Voronoi vertex
v
is
15
Image taken from (Fukuda, 2004)
Triangulations
Voronoi
Diagram is called the Delaunay
Triangulation.
(auto
-adjusted) Harris Corner Points is
computed
images
inthedatabasewithwhich theimageis
compared
two-by-two.Inotherwords,images
in
diagram
s.
Triangulations
Delaunay
Triangulation can be taken to be the
sites
position)
the vertices of the Voronoi diagram are
of
dual
graph (excluding the exterior face) will
be
triangulation
ofthesites,theDelaunaytriangulation.
Figure
29: Delaunay Triangulation
15
points
in
ℝ
n
.Theconvexhullconv(nb(S,v))
ofthe
called the Delaunay cell of
v. The
Delaunay
40
Triangulation.
The Delaunay
computed
on both the
tobecompared.
in
thedatabaseare
sites
themselves.
of
degree three, it
be
triangles. The
nearestneighbor
Delaunay
complex (or
41
triangulation)of
S
isapartitionoftheconvexhull
conv(S)
intotheDelaunaycellsofVoronoi
verticestogetherwiththeirfaces.
TheDelaunaycomplexisnotingeneralatriangulationbutbecomesatriangulationwhen
the input points are in
general position
(or
non-degenerate
), i.e. no n+2
points are co-
sphericalorequivalentlythereisnopointc∈
ℝ
n
whosenearestneighborsethasmorethan
n+1
elements.
6.3.3.PropertiesofDelaunayTriangulations
Delaunaytriangulationshaveanumberofinterestingpropertiesthatareconsequencesof
thestructureoftheVoronoidiagram.
Convex hull: TheexteriorfaceoftheDelaunay triangulationistheconvex hullofthe
pointset.
Circum-circleproperty:Thecircum-circleofanytriangleintheDelaunaytriangulation
isempty(containsnositesofP).
Emptycircleproperty:Twositesp
i
andp
j
areconnectedbyanedgeintheDelaunay
triangulation,ifandonlyifthereisanemptycirclepassingthroughp
i
andp
j
.
Closest pair property: The closest pair of sites in P are neighbors in the Delaunay
triangulation. (The circlehavingthesetwosites asitsdiametercannotcontainanyothersites,
andsoisanemptycircle.)
Size:GivenapointsetPwithnsiteswheretherearehsitesontheconvexhull,inthe
plane,theDelaunaytriangulationhas2n–2–htriangles,and3n–3–hedges.
Ifthesitesarenotingeneralposition,inthesensethatfourormoreareco-circular,then
theDelaunaytriangulation maynot be a triangulationatall,butjustaplanargraph (sincethe
42
VoronoivertexthatisincidenttofourormoreVoronoicellswillinduceafacewhosedegreeis
equaltothenumberofsuchcells). Inthiscasethemoreappropriateterm would beDelaunay
graph.However,itiscommontoeitherassumethesitesareingeneralposition(ortoenforceit
throughsomesortofsymbolicperturbation)orelsetosimplytriangulatethefacesofdegreefour
ormoreinanyarbitraryway.MATLABensuresthattheresultingdiagramisatriangulation.
DelaunayTriangulationscanalsoberepresentedasgraphs,wheretheDelaunayedgesare
thegraph’sedges,andtheDelaunayverticesarethegraph’svertices.
43
7.
MATLAB
F
UNCTIONS
:
V
ORONOI
,
V
ORONOIN
,
D
ELAUNAY
T
RI
,
Q
HULL
7.1.Voronoi
Unfortunately for my choice of programming language, the most evident MATLAB
functiontouseinordertoobtainaVoronoidiagramonlyplotsthediagram,withoutreturning
anyrelevantinformationaboutitstopology.
TheMATLABfunctionvoronoi(x,y)plotstheboundedcellsoftheVoronoidiagramfor
the points x and y. Lines-to-infinity are approximated with an arbitrarily distant endpoint
(MathWorks,1984-2011).Thefunction’sdrawbackisthatitdoesnotreturnthelocationsofthe
Voronoiverticesoranyotherinformationregardingthetopology.
Figure 30: An Example of Voronoi Diagram Creation
AgeneratedVoronoidiagramfromasetofpointsintheplaneisshowninFigure30.To
the left, we have the original set of points, and to the right we have the generated Voronoi
diagram,whichisobtainedbycallingvoronoionthearraythatcontainsthecoordinatesofthe
originalpoints,thespecificcallbeingvoronoi(x,y).Everypointontheedgeisequidistantfrom
the generating points in the two adjacent cells, and everypoint where three edges intersect is
44
equidistantfromthegeneratingpointsofthethreeadjacentcells. InFigure31,thevaluesofx
andyforthefigurearerepresented,aswellasthevalueofXwhichisusedinthenextsection.
x y X
1
1
1
1
1
499
1
499
145
144
145
144
217
288
217
288
288
433
288
433
362
74
362
74
499
1
499
1
499
499
499
499
Figure 31: The Values for the Coorfinates of the Generating Set of Figure 30
7.2.Voronoin
For the topology of the Voronoi diagram, i.e., the vertices for each Voronoi cell, one
needstouseanotherfunctionprovidedbyMATLAB,voronoin.
The voronoin function uses the Qhull algorithm first described in (Robertson,Sanders,
Seymour,&Thomas,1996)andexplainedinSection8.4ofthisdocument.
Thesyntaxofthevoronoinfunctionis[V,C]=voronoin(X)(MathWorks,1984-2011).
TheinputXisanm-by-narray,representingmn-dimensionalpointsthatconstitutethecenters
oftheVoronoicells(thegeneratingsetforthediagram),wheren>1andm≥n+1.Inourcase,
sincewearedealingwith2Dimages,n=2.Xisbasicallytheconcatenationofxandy,sincec
representsthex-coordinatesofthepointsandrrepresentsthey-coordinatesofthepoints.Xis
alsorepresentedinFigure31.
The function returns the Voronoi vertices V and the Voronoi cells C of the Voronoi
diagram of X. Here, V is an array of dimension k-by-n, where each row represents the
n-dimensionalcoordinatesoftheVoronoivertex;inourcasen=2.ThefirstrowofVisapoint
atinfinity.
45
V C
Inf
Inf
[9,2,1,8]
-
103.267
250
[5,3,2,1,4]
16.13
4
298.433
[9,2,3,6]
250
924.765
[11,5,3,6]
133.624
418.708
[11,5,4,10]
273.15
3
169.92
4
[11,6,9,8,7,10]
543.7
30
250
[8,1,7]
250
-
301.246
[10,4,1,7]
200.35
6
-
55.746
451.794
279.63
6
427.76
2
274.682
Figure 32: Vertice and Cell Arrays for the Voronoi Diagram in Figure 30
Asdiscussedinthechapterongraphrepresentations,thearrayCisanarrayofcyclesin
theVoronoigraph;inMATLAB,Cisofaspecialdatatype,thevectorcellarray(MathWorks,
1984-2011).EachelementofCcontainstheindicesintoVoftheverticesofthecorresponding
Voronoicell,inconsecutiveorder,suchthatthereisanedgebetweentwoconsecutiveverticesas
wellasbetweenthefirstandlastone.
Ifanyindexinacellofthecellarrayis1,thenthecorrespondingVoronoicellcontains
thefirstpointinV,apointatinfinity.ThismeanstheVoronoicellisunbounded.
Unbounded Voronoi cells create problems with the conditions for the threshold auto-
adjustment programin Section 9. This can be overcome eitherbyignoring the respective cell
(butloosingperhapsrelevantinformation)orbyusingtheimageborderasalimit(Section9).
TheresultofusingvoronoinontheXinFigure31isshowninFigure32.
ItisinterestingtonotethatinordertoshowtheVoronoidiagramitissufficienttocall
the voronoi function, whilein orderto retain anyusefulinformation it is necessarytousethe
voronoinfunction.IamsurethereisthewaytoaccuratelyplottheVoronoidiagramusingthe
information from voronoin (thus avoiding recomputing the same information), but as of this
46
version of the project, voronoin is used to gather useful information and voronoi is used to
accuratelyplotthediagram.
7.3.DelaunayTriandtriplot
ThefunctiontocomputetheDelaunayTriangulation thatisusedinthisprojecthas the
formDT=DelaunayTri(x,y)
16
.ItcreatesaDelaunaytriangulationfromasetofpoints,specified
ascolumnvectors,eachcolumnrepresentingthexorycoordinatesofthepoints.
Figure 33: Delaunay Triangulation of the Points from Figure 30-left
The function used to accurately plot the computed triangulation is triplot(TRI,x,y)
17
. It
displaysthetrianglesdefinedinthem-by-3matrixTRI.ArowofTRIcontainsindicesintothe
vectorsxandythatdefineasingletriangle.Thedefaultlinecolorisblue.
TheresultintherunningexamplefromFigure30isshowninFigure33.
16
(MathWorks, 1984-2011)
17
(MathWorks, 1984-2011)
47
7.4.TheQuickhullAlgorithm
MATLABusesthequickhullalgorithm(Qhull)tocomputebothVoronoiDiagramsand
Delaunay Triangulations. The algorithm was first described in 1996 in (Barber, Dobkin, &
Huhdanpaa,1996)
ThefollowingistakenfromtheQhullmanual,in(Qhull.org,1995).
The convex hull of a set of points is the smallest convex set that contains the points.
Qhullcomputestheconvexhullin2D,3D,4D,andhigherdimensions.Thealgorithmissimilar
to is similar to the randomized, incremental algorithms for convex hull and delaunay
triangulation.IfthesetSisfinite,theconvexhulldefinesamatrixAandavectorbsuchthatfor
allxinS,Ax+b<=[0,...].
Qhullrepresentsaconvexhullasalistoffacets.Eachfacethasasetofvertices,asetof
neighboringfacets,andahalf-space.Ahalf-spaceisdefinedbyaunitnormalandanoffset(i.e.,
a row of
A
and an element of
b). Qhull accounts for round-off error. It returns "thick" facets
definedbytwoparallelhyper-planes.Theouterplanescontainallinputpoints.Theinnerplanes
exclude all output vertices. Qhull may be used for the Delaunay triangulation or the Voronoi
diagramofasetofpoints.Itmayalsobeusedfortheintersectionofhalf-spaces.
48
\
8.
A
UTOMATIC
T
HRESHOLD
A
DJUSTMENT
Theoriginalversionoftheprogramallowedtheusertoselecttheparametersmanually,
fromafiguresimilartotheoneinFigure34.Itsoonbecameapparenthoweverthatinorderfor
the desired seamless image duplicate detection, we needed the program to auto-adjust the
threshold value when detectingthe corner points. It was unexpected, however, that I couldn’t
findanygoodpaperouttheretodoparameteradjustmentthewayIdesired.SoIdecidedtowrite
myown.
Figure 34: Harris Corner Points Parameter Selection Window
Ichosetoonlymodifythethreshold,andkeepthevaluesofsigma(standarddeviationof
smoothingGaussian)andradius(radiusofregionconsideredinnonmaxsuppression)to1and2,
respectively. Changing only the threshold should allow for as much flexibility as need, while
simplifyingtheprogram.
49
8.1.Purpose
Inordertomatchtwonear-duplicateimages,weneedtogettwographsthatareasclose
to each other as possible, representing the images. By applying the same threshold on two
images, one of them being the near-duplicate of the other, we can and will obtain different
results,dependingonwhattypeofimagemodificationwasdone.Ifthenear-duplicateimagewas
subjectedtoonlygeometricchangesotherthanchangesinscalesincescaleaffectsthenumberof
cornerpointsdetectedaslongasthethresholdvalueisconstant(referbacktochapters3and5),
then the graph of thesecondimagewill most likelybe a subgraph of the original graph, or a
graphisomorphictoit.Ifthesecondimagewassubjectedto(linear)photometricimagechanges
though,thereismorelikelythatthenewgraphwouldbeasubgraphoraminoroftheoriginal
graph(ortheotherwayaround). Inthiscasethen,alimitonwhatconstitutesasubgraphora
minorshouldbeplaced,soastolimitthenumberoffalsepositivesobtained.
8.2.Preliminaries
The conditions the Voronoi diagram needs to meet in order for the threshold that
generatedtheHarrisCornerPointssetthatunderliesthediagramareexpressedbelow,insection
8.3.Butfirst,Ineedtoexplainsomepreliminaries.
LetWbethewidthoftheimage,andHbetheheight.Then,theareaoftheimageisA=
W∙H. Let numcells be the number of cells in the Voronoi Diagram, computed based on the
resultingHarrisCornerPointsgeneratedusingasetpreliminarythreshold,thr.Thennumcellsis
alsothenumberofCornerPointsdetected.
Thethresholdadjustmentprogramisbasedontheareasofeachcell,Ac
i
,asrelatedtothe
areaoftheimage.Sincevoronoinworksinsuchawaythatthefirstrowofvertexcoordinatesis
50
[Inf Inf], the cells that contain this first vertex have an infinite area, so in order for a more
accuratearea,consideringthepictureisfinite,wecouldeitherdisregardtheseareasortakethe
polygons relative to the margins of the picture. Right now, I am disregarding these areas by
makingthemcomplywiththeconditionsin8.3,nomatterwhattheirarearelativetotheimage
borderis.InFigure35(a)forexample,thecellsonthemarginsaredisregardedsincetheyhave
aninfinitearea(theactualresultisNaN);anotheroptionwouldbetocalculatetheareaofthe
visiblepartofthecell.
Figure 35: Voronoi Diagrams (a) with threshold 5,000; (b) with threshold 15,000
8.3.Conditions
Althoughitisnotguaranteedtogivethebestpossiblethresholdforanimage,theauto-
adjustingprogramasitiswrittenrightnowwill adaptdependingontheimagesizeandsome
characteristics of the Voronoi Diagram based on a preliminary set of Harris Corner Points,
generatedgivenasetthreshold.Sincewearestartingwithasmallvalueforthethreshold(thr=
100initially)andincreasingitfromthere,weknowthatwewillkeepthesmallestvalueofthe
51
thresholdencounteredthatgeneratesadiagramcomplyingwiththeconditions.Thismeansthata
valueforthethresholdofthr=5000(Figure35(a))willneverbereached(thoughtheoptimal
valueofthr=2,500won’tbeestablishedeither).
TherearefourconditionsimposedonthecellsoftheVoronoiDiagram,aswellasonthe
numberofHarrisCornerPointsperimageinordertoauto-adjustthreshold,asfollows:
1. The biggest cell area has to be smaller than one fourth the area of the image, or
p?q
O
r
s
t
u
.Inotherwords,therewillbenocellintheimagebiggerthan,orequal
to,aquarteroftheimage.ThediagraminFigure35(b)wouldviolatethiscondition.
2. All cell areas have to be bigger than the area of the image over numcells
2
, that is,
v@
F
w
t
Vxyz{{|
"
.Thissetsarelativelimitastohowsmallthesmallareasareallowed
tobe.Furtherlimitsapplythough,asexpressedbelow.
3. Thesumoftheareasthataresmallerthantheareaoftheimageovernumcellsisless
than the area of the image over numcells, that is,
O
rr
s
t
Vxyz{{|
, for all i= {1,
2,…,numcells}whereO
r
s
t
Vxyz{{|
.
4. The number of corner points detected, numcells, has to be at least one fifth of the
squarerootoftheareaoftheimage,thatisT)U}}~
t
;thisconditionhastobe
met even if the ones above aren’t met: the program stops execution once this
conditionisnotmet,regardlessofwhetherornotoneoftheotherconditionsismet.
Thisempiricalnumberofpointsisbasedontheassumptionthattheimageisinsome
sensesignificant.
52
8.3.Algorithm
functionthr=adjust_thresh(img)
%img=imread('photos_in/022.jpg');
img=rgb2gray(img);
%getthewidthandheightoftheimage,andcomputethearea
[w,h]=size(img);
A=w*h;
[thrmeet]=adjust_thresh1(100,A,img);
whilemeet==1
[thrmeet]=adjust_thresh1(thr,A,img);
%disp(thr);
end;
function[thrmeet]=adjust_thresh1(thr,A,img)
%thristhethreshold,eventuallyadjustedatthisstep
%AisW*H
%meetis1ifconditionsaremet,soweneedtocontinue
%findtherowandcolumncoordinatesoftheHarrisCornerPoints
[~,r,c]=harris(img,1,thr,2);
x=[];
x(:,1)=c;
x(:,2)=r;
%findthecoordinatesoftheverticesoftheVoronoidiagram,
%aswellaswhichverticescomposethecellsofthediagram
[vert,cell]=voronoin(x,{'Qbb','Qz'});
%thenumberofcells
numcells=length(cell);
%thefractionoftheimagearea
An=A/numcells;
%disp(['An='num2str(An)]);
%freeupsomememory
clearvarsxrc;
%thesumofall"small"areas
S=0;
%themaximum
Ac_max=0;
%meetis1ifoneoftheconditionsismet,and0ifnot
meet=0;
%meet==1when:
53
%*Ac_max>=A/4
%*Ac<=A/numcells^2
%*S>=A/numcells,whereS=Sum[Ac|Ac<A/numcells]
%meet==0,evenifaboveconditionsaremet,if:
%*numcellss<sqrt(A)/5
fori=1:numcells
%numberofverticesincelli
len=length(cell{i});
%XYisamatrixofthevertexcoordinates
XY=zeros(2,len);
forj=1:len
%thexcoordinateofthej'thvertexofcelli
XY(1,j)=vert(cell{i}(j),1);
%theycoordinateofthej'thvertexofcelli
XY(2,j)=vert(cell{i}(j),2);
end;
%calculatetheareaofthecurrentcell
Ac=polyarea(XY(1,:),XY(2,:));
%iftheareacontainsavertexatinfinity,ignorethiscell
if(isnan(Ac))
Ac=An;
end;
%calculatethemaximum
ifAc>Ac_max
Ac_max=Ac;
end;
if(Ac<=A/(numcells*numcells))
meet=1;%ift
else
%calculateS
if(Ac<An)
S=S+Ac;
%disp(['S='num2str(S)]);
end;
end;
end;
if(Ac_max>=A/4)||(S>=An)
meet=1;
end;
if(numcells<sqrt(A)/5)
meet=0;
end;
if(meet==1)
thr=thr+100;
end;
Code Snippet 10: The Threshold Auto-Adjust Function
54
The 3-channel image is first converted to grayscale and its area, A, is computed. The
program starts with a preliminary threshold thr = 100, and tests if that isenough to meet the
conditions. The conditions are met if meet == 0, and the program increases the threshold if
meet==1.ThecoordinatesoftheHarrisCornerPointsaswellasthecoordinatesoftheVoronoi
verticesarecomputed;thenumberofcornerpoints/Voronoicellsisretainedinnumcells.The
variableAnretainsthevalueofthefractionA/numcells.
Foreverycell,theareaofthecell,Ac,iscomputed;iftheareaisnotanumber(NaN),
thenitisassignedavaluethatwouldmeettheconditions,An.Ifcondition(2)fromSection8.2is
notmet,thentheconditionsarenotmet:meet=1.Otherwise,iftheareaofthecurrentcellis
smallerthanAn,itisaddedtothesumofthesmallareas.Similarly,ifthecurrentareaisbigger
thanthemaximumareauntilnou,Ac_max,thecurrentareabecomesthemaximum.
Aftergoingthroughallthecells,conditions(1)and(3)fromSection8.2areverified,and
ifneitheroneismet,thenmeet=1.Intheend,thelastcondition,(4),ischecked.Ifitisnotmet,
thenthecurrentthresholdisenough,so,meet=0.
Iftheconditionsarenotmet,thenthethresholdincreasesby100,andtheprevioussteps
arerepeated.
8.4.Problems
Theprogramruntimeisquadraticinthe number ofcells!Theremightbewaysaround
thisproblem(aDivideandConqueralgorithmforstarters),butIhavenotyetaddressedthem.
ThewayaroundthisthatIworkedonforpresentingtheprojectisrunningitallonce,savinga
text file with the name of the file and of the threshold, and using this file to lookup the
appropriatethresholdforeachimage.Ofcoursesuchanapproachtakesalotoftimeforthefirst
55
runoftheprogram,andishighlyunreliablesinceausercanmanuallychangethenameofthe
filetotrickthesystem,butthatisnotthepurposeofthisproject.
Imagesthataddtextoranysortofhighlyconcentratednumberofpointsareconfusing
forthesystem(see).Thatis,imagesthatdifferfromtheoriginalimagebyaddingtext canbe
problematic.Myfirstversionoftheprogramwashighlyconfusedbytextaddedintheimage,but
thenewerversiondealsbetterwithit.Nevertheless,sincetheprojectonlyexploresthetypesof
image changes that were described in Section 3, this problem doesn’t matter in light of the
current research question. It is interesting to note however that someone who has knowledge
regardingthisissuecaneasilytricktheprogram.
Theprogramdoesnotcomputetheperfectthreshold.Betterthresholdscouldbegivento
theprogrambyauser.Also,thethresholdstheprogramcomesupwithdonotguaranteethatthe
samepointswillbecomputedinnear-duplicates,andthusdoesnotconformtothewindowing
function in Section 4.6.Nevertheless, computing the threshold in this way allowsfora finite,
boundeddimensionofthegraphsgenerated.
Also,thresholdvaluesincreaseinstepsof100,sothethresholdisnotnecessarilyexact.
A better approach would be to start decreasing the thresholdsin smaller and smaller steps in
order to coin the best value. Nevertheless, since the program cannot come up with the best
possiblethresholdbydesign,thereisnoreasontoslowitdownevenfurther.
56
9.
E
NCODINGAN
I
MAGEASA
G
RAPH
:
D
ELAUNAY
T
RIANGULATIONS
9.1.Methodology
The premise of the project is thatimagescanbe encodedas graphs, and that thereare
somebenefitsinencodingthemassuch.Thereasontochoosegraphsasopposedtojustcorner
pointscomesfromthebeliefthatpeopleandmachinesshouldbeabletoperformthesametask
in a transparent way, and matching points is something that we think people find more
complicatedthanmatchinggraphs.
SinceHarrisCornerPointsworkfairlywell in identifyingsomeduplicateimages,they
have been chosen to be used as a basis for creating more suggestive graph-encodings of the
images.The Voronoi Triangulation seemed like the natural choice, but itturnedoutto be too
unstable,changingtooeasilywhenpointswereaddedorremoved.TheDelaunayTriangulation,
althoughthedualgraphoftheVoronoiDiagram,provedtobemorestableforthepurposesof
ourproject.
Thealgorithmthatconvertsanimageintoagraphisfairlysimple:
1. Givenanimage,wecancomputethepreliminaryHarrisCornerPointsonitanduse
the threshold adjustment algorithm described earlier to auto-adjust the threshold to
themostappropriatevalue;
2. Given the new threshold, we can recompute the best Harris Corner Points on the
image;
3. Given the locations of the Harris Corner Points, we can use the DelaunayTri
MATLABfunctiontocomputetheDelaunayTriangulation,andsavetheresultasthe
57
graphical encoding of the image – this graph can be weighted or unweighted: for
now,wearesavingitasanunweightedgraph.
Figure 36: Steps in Obtaining a Graph from an Image
9.2.EncodingCode
[cim,r,c]=harris(img,1,thr,2);
dt=DelaunayTri(c,r);
triplot(dt);
Code Snippet 11: Delaunay Image Encoding
TherowandcolumncoordinatesoftheHarrisCornerPointsareretrieved,usingtheauto-
adjustedthreshold.TheDelaunayTriangulationiscomputedanddisplayed.
1. Automatic Threshold Adjusted Using Voronoi Diagram
2. Harris Corner Detector Using Appropriate Threshold
4. Delaunay Diagram Representation of the Image
3. Delaunay Diagram From Appropriate Harris Points
58
9.3.ProblemswithCurrentApproach.FuturePlans
EncodinganimageasaDelaunayTriangulationisjustlikehashing:twoimagescanhash
to very similar entries, but that won’t occur very often. I have not investigated what the
likelihoodoftwo differentimagesbeingencodedbysimilar(inthesensethisprojectassumes
similarity)diagramis.
Assuming the pictures are taken by different people, with different cameras and in
different positions, and that the pictures are of various natural scenes, then the likelihood of
havingtwopicturesofcompletelydifferentscenesencodetosimilardiagramsisverylow.
This likelihood would, most likely,go even lower if the graphs that we are comparing
were in fact weighted, with the weight representing the distance between the two respective
verticesthatrepresenttheendpointsoftheedge.
Aspartofmypossiblefutureplans(seeSection10.2),Iamplanningtoconductastudy
onhowpeopledecidewhatdiagramsarerelatedornot.Insuchacase,itisalmostcertainthat
thediagram4fromFigure36isabetterrepresentationoftheoriginalimageindiagram1than
thediagraminFigure37,althoughtheyarebothdiagramsofthesameimage.
Figure 37: Other Representation of the Delaunay Graph
59
Inotherwords,theplacementofvertices,aswell asthedistancesbetweenthem,most
likely matter for human observers; whether or not they should be taken into account when
writingaprogramthatfindsnear-duplicatesisanotherinterestingresearchquestion.
Right now, rather than deal with graphs that maintain the properties of the Delaunay
Diagram,theprogramonlymaintainstheverticesandconnectionsbetweenthemanddisregards
allotherinformation.
So,fortheprogramrightnow,Figure37anddiagram4ofFigure36arethesamegraph.
60
10.
R
ESULTS
.
C
ONCLUSIONS
.
F
UTURE
W
ORK
10.1.Results
The following pagesshow the images,cornerpoints, VoronoiDiagrams andDelaunay
Triangulationsforalltheconsideredtransformationsofanimage,includingtheoriginalimage.
The first image in the group (Figure 38, Figure 42, Figure 46, Figure 50, Figure 54,
Figure58,Figure66,Figure70,Figure74andFigure78)istheoriginalimageweareworking
with,foreverygroupofpictures.
Thesecondimageineachgroup(Figure39,Figure40,Figure44,Figure48,Figure52,
Figure64,Figure56,Figure60,Figure68,Figure72,Figure76andFigure80)provesthatthe
automatically detected threshold value produces acceptable corner points, for all images,
regardlessofmodifications.
The third image of the group (Figure 40, Figure 44, Figure 48, Figure 52, Figure 64,
Figure56,Figure60,Figure68,Figure72,Figure76,Figure80)showstheVoronoiDiagramfor
theimage,giventhethreshold.Itshows,inagraphicalway,howadiagramshouldlooklikein
orderforalltheconditionsforthethresholdauto-adjustmenttobemet(Section8.3).
The fourth image of the group (Figure 41, Figure 45, Figure49, Figure 53, Figure 65,
Figure 57, Figure 61, Figure 69, Figure 73, Figure 77 and Figure 81) shows the Delaunay
Diagram for the image, given the threshold. These constitute the graph representations that
shouldbecomparedinordertoseeifanimageisanear-duplicateoftheother.
Fortheoriginalimage(Figure38),thethresholdvalueobtainedisanappropriatevalue,
ascanbeseenfromtheobtainedcornerpointsinFigure39.AscanbeseeninFigure41,the
61
DelaunayDiagramdisregardspartsoftheimagethataren’tinteresting.Thecornerpointsthatare
ontheedgeoftheimagecouldbedisregardedintheimplementation.
•
Image“003.jpg”;auto-thresholdvalue:17,500
Figure 38: Original Image
Figure 39: Corner Points
Figure 40: Voronoi Diagram
Figure 41: Delaunay Triangulation
The same is true about the threshold value and the Delaunay Diagram for the auto-
contrasted(Figure42),blurred(Figure46),brighter (Figure50),darker(Figure54)andlarger
(Figure58)images.OnecanseethesimilaritybetweentheDelaunayDiagramsforallofthese
62
images,andtheworkingassumptionisthatthesegraphsareeithersubgraphsorminorsofone
another.
•
Image“003_autocontrast.jpg”;auto-thresholdvalue:15,300
Figure 42: Auto-Contrast Image
Figure 43: Corner Points
Figure 44: Voronoi Diagram
Figure 45: Delaunay Triangulation
63
•
Image“003_blur.jpg”;auto-thresholdvalue:300
Figure 46: Blurred Image
Figure 47: Corner Points
Figure 48: Voronoi Diagram
Figure 49: Delaunay Triangulation
64
•
Image“003_brighter.jpg”;auto-thresholdvalue:17,500
Figure 50: Brighter Image
Figure 51: Corner Points
Figure 52: Voronoi Diagram
Figure 53: Delaunay Triangulation
65
•
Image“003_darker.jpg”;auto-thresholdvalue:19,100
Figure 54: Darker Image
Figure 55: Corner Points
Figure 56: Voronoi Diagram
Figure 57: Delaunay Triangulation
66
•
Image“003_larger.jpg”;auto-thresholdvalue:15,100
Figure 58: Larger Image
Figure 59: Corner Points
Figure 60: Voronoi Diagram
Figure 61: Delaunay Triangulation
67
Thethresholdvalueforthecroppedimage(Figure62)isalsoappropriate.TheDelaunay
Diagramseemstobeasubgraphofthatoftheoriginalimage’s.
•
Image“003_crop.jpg”;auto-thresholdvalue:18,200
Figure 62: Cropped Image
Figure 63: Corner Points
Figure 64: Voronoi Diagram
Figure 65: Delaunay Triangulation
68
Areflectionmirrorstheimage,horizontally.Thethresholdofthereflectedimage(Figure
66)alsoproducesappropriatecornerpoints.Thegraphofthereflectedimageiseitherthesame
asthereflectedgraphoftheoriginalimage,orasubgraphofit.
•
Image“003_reflected.jpg”;auto-thresholdvalue:17,500
Figure 66: Reflected Image
Figure 67: Corner Points
Figure 68: Voronoi Diagram
Figure 69: Delaunay Triangulation
69
A90
o
rotationtotherightproducesathresholdthatisalittlebitlowerinvaluethanthe
threshold of the original image. The threshold of the rotated image (Figure 70)also produces
appropriate corner points. Since the threshold differs by 100, the graphs are likely not
isomorphic;theyareeithersubgraphsorminorsofoneanother.
•
Image“003_rotated.jpg”;auto-thresholdvalue:17,400
Figure 70: Rotated Image
Figure 71: Corner Points
Figure 72: Voronoi Diagram
Figure 73: Delaunay Triangulation
70
Shearingproducessomeartificialcornerpoints,aswellaschangesthedistancebetween
pointsontheimage.Thethresholdfortheshearedimage(Figure74)is,again,appropriate.The
Voronoi graph differs completely because of the artificial points, but the Delaunay graph is
again,similarforthenakedeye.
•
Image“003_sheared.jpg”;auto-thresholdvalue:11,800
Figure 74: Horizontally Sheared Image
Figure 75: Corner Points
Figure 76: Voronoi Diagram
Figure 77: Delaunay Triangulation
71
The only image transformation that creates problems in threshold auto-detection is the
smaller image (Figure 78). The threshold value is too big, and the number of corner points
detectedistoosmallcomparedtothecornerpointsfortheothertransformations.Asaresult,the
Delaunay Triangulation has a lot less points than that of the other images. Nevertheless, the
graphisclearlyrelatedtotheothers.
•
Image“003_smaller.jpg”;auto-thresholdvalue:45,700
Figure 78: Smaller Image
Figure 79: Corner Points
Figure 80: Voronoi Diagram
Figure 81: Delaunay Triangulation
72
10.2.ConclusionsandFutureWork
Someclaimsmadethroughoutthispaperhavenotbeenthoroughlyinvestigated,mainly
becauseoftheshortdurationoftheproject(roughly7months),thatincludedthetimetocomeup
with a research question, the time to do background reading on the material already existent
(Frolova & Simakov, March 2004) as well as the time for finding a niche that hasn’t been
explored before. Although Voronoi Diagrams have been explored as image segmentation
techniquesbefore(Arbelaez&Cohen,2003),(Sinclair,1999),(Cheddad,Mohamad,&Manaf,
2008),athresholdauto-adjustmentalgorithmbasedonfeaturesoftheimageVoronoiDiagram
has not been previously explored, at least not from what I found. Neither have Delaunay
Triangulationsbeenusedtoencodeimagecharacteristicsforduplicatedetectionbasedongraph
similarity.
ReferringbacktothedefinitionsinChapters5and6,therearesomesimilaritieswecan
inferbetweengraphsofimagenear-duplicates.Thesimilaritieshavebeenreferencedthroughout
thetext,andIwillsummarizethemhere.
• Identicalgraphs:twoDelaunaygraphsofthesameimagewouldbeidentical,aslongas
the threshold values are identical, bothin number of vertices, edge connections and in
vertexlabeling;ifwemovetoweightedgraphs,thegraphweightswillalsobethesame.
• If the thresholds detected would be adequately proportional, the graphs of scaled and
sheared images would also be identical to the original graph if the graphs are not
weighted; for changes in image size the graph weights would be proportional, and for
horizontalshearthedifferencewouldbemathematicallycomputable.
73
• The graphs of rotated and reflected images would be identical to the original image’s
graph,butwithdifferentvertexlabeling,thatistheywillbeisomorphic.
• Thegraphsofcroppedimageswouldbesubgraphsoftheoriginalimagegraph.
• The graphs of images obtained by blurring, contrast auto-adjustment, and changing
luminositywillconsistofeitherinducedsubgraphsorofminorsoftheoriginalgraph.
• Other measures that can be used to measure similarity are chromatic numbers and the
graphdiameter.
Nevertheless,wearenotdealingwithaperfectworld:thenumberofcornerpointsdiffers
betweenanimageanditsrotatedcounterpartforexample,evenifthesamethresholdisused.In
such a case, the only inference we can make is that the graphs of near-duplicates are either
(induced)subgraphsorminors.
Ididn’thaveenoughtimetotestthishypothesis,andtherearealsosomeproblemsthat
werenotforeseen,inthesensethatperformingthesimilaritysearchongraphsisnotpossiblein
MATLAB,andsomeofthecalculationsareevenNP-complete.Awayaroundthefirstproblem
would be exporting the resulting graphs in a format readable by Wolfram Mathematica and
importingthemthereinordertouse that softwaretoperformthesimilaritycomparison.Also,
sincewearedealingwithfinitegraphsthathavearelativelysmallnumberofvertices,abrute-
forceapproachtosolvingthoseproblemscanbetaken.
Anotherproblemwiththecurrentideaisthefactthatweareconsideringthegraphsas
beingunweighted,losingimportantinformationasaresult. Analternateapproachwouldbeto
retain the distance between vertices as the edge weight, and export the weighted graph to
74
Mathematica. Then again, the notions of minors and induced subgraphs were not defined for
weightedgraphs,andsuchaspecificationwillneedtobemade.
Anotherimportantissuethatnecessitatesworkisimprovingtherun-timeofthethreshold
auto-adjustmentmethod.Therearevariouswaystoimproveuponthequadraticalgorithm,such
asusingaDivideandConquerapproach.
Aninterestingfuturestepinthedevelopmentoftheprojectwouldbetodesignastudyin
whichpeoplearepresentedwithDelaunayDiagrams,suchastheonesinFigure41andFigure
45andaskedtosaywhetherthetwographsareencodingsofnear-duplicates.Whenpresented
withgraphsofatleastahundredimages,itmightbecomeapparentwhatcriteriapeopleuseto
classify those graphs. Also, an interesting improvement upon the experiment might ask the
subjects to identify which graph belongs to which transformation, and see if any useful
conclusionscouldbedrawnfromthere.
Inconclusion,Ibelievethat,duringthistwosemester-longproject,Iwasabletocomeup
withaninterestingidea,thathasthepotentialtoworkandalsooffersanewwaytoviewimages,
aswellasmadethefirststepstowardsitsimplementation.IbelievethatthesekindsofDelaunay
graphrepresentationsofimagescanbeusefulwhensearchingfornearduplicates,especiallyif
the image by which you are actually searching is not-to-be-disclosed to the owners of the
database.
75
Bibliography
Ahn, S. H. (2005). Convolution. Retrieved April 11, 2011, from
http://www.songho.ca/dsp/convolution/convolution.html
Arbelaez, P. A., & Cohen, L. D. (2003). Generalized Voronoi Tessellations for Vector-Valued Image
Segmentation. Proc. 2nd IEEE Workshop on Variational, Geometric and Level Set Methods in Computer
Vision (VLSM'03) (pp. 49-56). Nice, France: IEEE.
Aurenhammer, F. (n.d.). Voronoi Diagrams - A Survey of a Fundamental Geometric Data Structure. 345.
Aurenhammer, F., & Klein, R. (2000). Handbook of Computational Geometry (Vol. Ch. 5: Voronoi
Diagrams). (J.-R. Sack, & J. Urrutia, Eds.) Amsterdam, Netherlands: North-Holland.
Barber, C. B., Dobkin, D. P., & Huhdanpaa, H. T. (1996). The Quickhull Algorithm for Convex Hulls. ACM
Trans. Mathematical Software , 22, 469-483.
Bondy, J. A., & Murty, U. S. (1976). Graph theory with applications. New York: Elsevier Science Publishing
Co.
Cheddad, A., Mohamad, D., & Manaf, A. A. (2008). Exploiting Voronoi diagram properties in face
segmentation and feature extraction. Pattern Recognition , 41, 3842-3859.
Dirichlet., P. G. (1850). Uber die Reduction der positiven quadratischen Formen mit drei unbestimmten
ganzen Zalhen. J. Reine Angew. Mathematik , 40, 209–227.
Du, Q., Faber, V., & Gunzburger, M. (1999). Centroidal Voronoi Tessellations: Applications and
Algotithms. SIAM REVIEW , 41 (4), 637-676.
Foo, J. J., Zobe, J., & Sinha, R. (2007). Clustering Near-Duplicate Images in Large Collections. Proceedings
of the international workshop on Workshop on multimedia information retrieval , 21-30.
Frolova, D., & Simakov, D. (March 2004). Matching with Invariant Features. The Weizmann Institute of
Science.
Fukuda, K. (2004, June 18). Frequently Asked Questions in Polyhedral Computation. Retrieved 04 17,
2011, from http://www.ifor.math.ethz.ch/~fukuda/polyfaq/polyfaq.html
Hadwiger, M. (1998). Mesh Simplification and Multiresolution Data Structures. Retrieved April 22, 2011,
from Mesh Simplification and Multiresolution Data Structures
Harris, C., & Stephens, M. (1988). A Combined Corner and Edge Detector. Proceedings of the 4th Alvey
Vision Conference , 147-151.
76
MathWorks. (1984-2011). MATLAB - Documentation. Retrieved April 11, 2011, from
http://www.mathworks.com/help/techdoc/
Moravec, H. (1980). Obstacle Avoidance and Navigation in the Real World by a Seeing Robot Rover.
Pittsburgh: Carnegie-Mellon University, Robotics Institute.
Moravec, H. (1979). Visual mapping by a robot rover. Int. Joint Conf. on Artif. Intell. , 598–600.
Noble, A. (1989). Descriptions of Image Surfaces. Oxford University: Department of Engineering Science.
Okabe, A., Boots, B., Sugihara, K., & Chiu., S. N. (2000). Spatial Tesselations: Concepts and Applications of
Voronoi Diagrams, 2nd ed. Wiley.
Pless, R. (2003). Spring 2003 Computational Geometry, Lectures 16 and 17. Retrieved April 22, 2011,
from http://research.engineering.wustl.edu/~pless/506/l16.html
Qhull.org. (1995, May 17). Qhull code for Convex Hull, Delaunay Triangulation, Voronoi Diagram, and
Halfspace Intersection about a Point. Retrieved April 22, 2011, from http://www.qhull.org/
Robertson, N., Sanders, D. P., Seymour, P. D., & Thomas, R. (1996). A New Proof of the Four Colour
Theorem. Electron. Res. Announc. Amer. Math. Soc. 2 , 17-25.
Rosenlicht, M. (1985). Introduction to Analysis. Dover Publications.
Sinclair, D. (1999). Voronoi seeded colour image segmentation. Cambridge, UK: AT&T Laboratories.
Voronoi, G. M. (1908). Nouvelles applications des parametres continus a la theorie des formes
quadratiques. deuxieme memoire: Recherches sur les paralleloedres primitifs. J. Reine Angew.
Mathematik , 134, 198-287.
West, D. B. (1996, 2001). Introduction to Graph Theory - Second Edition. Prentice Hall.
William, J., & Hirschfeld, P. (2001). Surveys in combinatorics. Cambridge, UK: Cambridge University
Press.
Winter, D. (n.d.). Planar Graphs. Retrieved April 22, 2011, from University of Michigan:
http://www.math.lsa.umich.edu/mmss/coursesONLINE/graph/graph5/
Wolfram Research. (2011, 04 22). Wolfram MathWorld. Retrieved 04 22, 2011, from
http://mathworld.wolfram.com/
77
T
ABLE
O
F
F
IGURES
Figure 1: Original Image ................................................................................................................................ 6
Figure 2: Cropped Image ............................................................................................................................... 7
Figure 3: Scaled Images (Up and Down) ........................................................................................................ 7
Figure 4: Image Rotated 90
o
Right ................................................................................................................ 8
Figure 5: Blurred Image ................................................................................................................................. 8
Figure 6: Horizontally Reflected Image ......................................................................................................... 9
Figure 7: Auto-Contrasted Image ................................................................................................................ 10
Figure 8: Lighter and Darker Images ........................................................................................................... 11
Figure 9: Horizontally Sheared Image ......................................................................................................... 11
Figure 10: Harris Corner Detector .............................................................................................................. 13
Figure 11: Autocorrelation Function Graphical Representation ................................................................ 15
Figure 12: Classification of Image Points Based on Response Size Using the Eigenvalues of M ................ 15
Figure 13: Harris Corner Point Detection Workflow .................................................................................. 17
Figure 14: Rotation Invariance
.................................................................................................................... 18
Figure 15: The Harris Corner Detector is Not Invariant to Image Scaling
................................................... 18
Figure 16: Partial Invariance to Affine Intensity Change
........................................................................... 19
Figure 17: Graph (G) Example ..................................................................................................................... 23
Figure 18: Example of Walk, Trail, Path, and Cycles.................................................................................... 24
Figure 19: A Directed Graph ........................................................................................................................ 25
Figure 20: The Cube Graph; Edge Crossing; Planar Representation .......................................................... 26
Figure 21: Faces of a Graph ........................................................................................................................ 27
Figure 22: Dual Graphs ................................................................................................................................ 27
Figure 23: Contracting edge v
1
v
2
to vertex ` ............................................................................................... 30
Figure 24: Graph Coloring Examples with χ = 3 ........................................................................................... 30
Figure 25: Graph Diameter Example .......................................................................................................... 31
Figure 26: Graph G
1
Representations .......................................................................................................... 32
Figure 27: Graph G
2
Representations .......................................................................................................... 32
Figure 28: Voronoi Diagram ....................................................................................................................... 38
Figure 29: Delaunay Triangulation ............................................................................................................. 40
Figure 30: An Example of Voronoi Diagram Creation ................................................................................. 43
Figure 31: The Values for the Coorfinates of the Generating Set of Figure 30 ........................................... 44
Figure 32: Vertice and Cell Arrays for the Voronoi Diagram in Figure 30 ................................................... 45
Figure 33: Delaunay Triangulation of the Points from Figure 30-left ......................................................... 46
Figure 34: Harris Corner Points Parameter Selection Window ................................................................... 48
Figure 35: Voronoi Diagrams (a) with threshold 5,000; (b) with threshold 15,000 .................................... 50
Figure 36: Steps in Obtaining a Graph from an Image ................................................................................ 57
Figure 37: Other Representation of the Delaunay Graph ........................................................................... 58
Figure 38: Original Image ............................................................................................................................ 61
Figure 39: Corner Points .............................................................................................................................. 61
Figure 40: Voronoi Diagram ........................................................................................................................ 61
78
Figure 41: Delaunay Triangulation .............................................................................................................. 61
Figure 42: Auto-Contrast Image .................................................................................................................. 62
Figure 43: Corner Points .............................................................................................................................. 62
Figure 44: Voronoi Diagram ........................................................................................................................ 62
Figure 45: Delaunay Triangulation .............................................................................................................. 62
Figure 46: Blurred Image ............................................................................................................................. 63
Figure 47: Corner Points .............................................................................................................................. 63
Figure 48: Voronoi Diagram ........................................................................................................................ 63
Figure 49: Delaunay Triangulation .............................................................................................................. 63
Figure 50: Brighter Image ............................................................................................................................ 64
Figure 51: Corner Points .............................................................................................................................. 64
Figure 52: Voronoi Diagram ........................................................................................................................ 64
Figure 53: Delaunay Triangulation .............................................................................................................. 64
Figure 54: Darker Image .............................................................................................................................. 65
Figure 55: Corner Points .............................................................................................................................. 65
Figure 56: Voronoi Diagram ........................................................................................................................ 65
Figure 57: Delaunay Triangulation .............................................................................................................. 65
Figure 58: Larger Image ............................................................................................................................... 66
Figure 59: Corner Points .............................................................................................................................. 66
Figure 60: Voronoi Diagram ........................................................................................................................ 66
Figure 61: Delaunay Triangulation .............................................................................................................. 66
Figure 62: Cropped Image ........................................................................................................................... 67
Figure 63: Corner Points .............................................................................................................................. 67
Figure 64: Voronoi Diagram ........................................................................................................................ 67
Figure 65: Delaunay Triangulation .............................................................................................................. 67
Figure 66: Reflected Image .......................................................................................................................... 68
Figure 67: Corner Points .............................................................................................................................. 68
Figure 68: Voronoi Diagram ........................................................................................................................ 68
Figure 69: Delaunay Triangulation .............................................................................................................. 68
Figure 70: Rotated Image ............................................................................................................................ 69
Figure 71: Corner Points .............................................................................................................................. 69
Figure 72: Voronoi Diagram ........................................................................................................................ 69
Figure 73: Delaunay Triangulation .............................................................................................................. 69
Figure 74: Horizontally Sheared Image ....................................................................................................... 70
Figure 75: Corner Points .............................................................................................................................. 70
Figure 76: Voronoi Diagram ........................................................................................................................ 70
Figure 77: Delaunay Triangulation .............................................................................................................. 70
Figure 78: Smaller Image ............................................................................................................................. 71
Figure 79: Corner Points .............................................................................................................................. 71
Figure 80: Voronoi Diagram ........................................................................................................................ 71
Figure 81: Delaunay Triangulation .............................................................................................................. 71
79
T
ABLE
O
F
C
ODE
S
NIPPETS
Code Snippet 1: Image Cropping ................................................................................................................... 7
Code Snippet 2: Image Scaling ...................................................................................................................... 7
Code Snippet 3: Image Rotation, 90
o
Right ................................................................................................... 8
Code Snippet 4: Image Blurring ..................................................................................................................... 8
Code Snippet 5: Image Reflection ................................................................................................................. 9
Code Snippet 6: Image Auto-Contrast ......................................................................................................... 10
Code Snippet 7: Image Brightness............................................................................................................... 10
Code Snippet 8: Image Horizontal Shear ..................................................................................................... 11
Code Snippet 9: Harris Corner Detector Function ...................................................................................... 21
Code Snippet 10: The Threshold Auto-Adjust Function .............................................................................. 53
Code Snippet 11: Delaunay Image Encoding ............................................................................................... 57
